4.2.1.1 Data structures and abstract data types Quiz: AQA Computer Science, Unit 2

The 20 questions

1. What is a data structure?

   • A single variable holding one value, which is used to store one item at a time in memory
   • A way of organising and storing data so it can be used efficiently
   • A programming language keyword, which is reserved so that it cannot be used as a name
   • A type of loop used to repeat code, with a counter that controls how many times it runs

2. What is an abstract data type (ADT)?

   • A description of a set of values and the operations that can be performed on them, independent of implementation
   • A programming language used for queues, where the queue operations are built into the syntax itself
   • A data structure that can only store integers, held in one fixed-size block of memory for speed
   • A file format used for binary data, which stores each record with a header and a checksum value

3. Which is a static data structure?

   • A linked list that grows as items are added
   • An array with a fixed size set when it is created
   • A tree that can gain nodes at runtime
   • A hash table that resizes automatically

4. Which is a dynamic data structure?

   • A linked list whose size changes as items are added and removed
   • A constant holding a single value, which is fixed in the program and cannot be changed later
   • An array of fixed length 10, whose size is set when it is created and cannot change after that
   • A record with a fixed set of fields, which holds the same number of values for every use

5. What is a disadvantage of a static data structure compared with a dynamic one?

   • It always runs slower than any dynamic structure, because each access checks its size first
   • It may waste memory if fewer items are stored than its fixed size, or fail if more are needed
   • It cannot be stored in memory at all, so it must be recreated from scratch on each run
   • It cannot store any data, so every value must be kept in a separate file on disk instead

6. Which is an advantage of a dynamic data structure?

   • It never needs to allocate memory
   • It can grow or shrink to fit the amount of data being stored
   • It is always faster to search than an array
   • It always uses less memory than any static structure

7. Which of these is an ADT that uses a first-in, first-out order?

   • Tree
   • Stack
   • Graph
   • Queue

8. Which of these ADTs uses last-in, first-out order?

   • Stack
   • Hash table
   • Dictionary
   • Queue

9. A dictionary is an ADT. Which description best fits it?

   • A tree with a single root
   • A list of items that can only be accessed by position in order
   • A stack of items with a peek operation
   • A collection of key-value pairs where a value is accessed through its key

10. Which ADT is best suited to storing a set of key-value pairs such as a phone book, where each name gives a number?

    • Stack
    • Dictionary
    • Binary file
    • Queue

11. Which is a vector in the context of abstract data types?

    • An ordered collection of values accessed by index
    • A hash table with collisions, where two keys share a slot and are handled by probing
    • A graph with weighted edges, where each connection carries a numerical cost between nodes
    • A stack of frames, with each frame holding the return address and locals of one call

12. What is the main difference between an ADT and its implementation?

    • The ADT defines the operations and behaviour, while the implementation defines how they are coded
    • The implementation is the same as the ADT but stored on disk, so it can be read later by the program
    • There is no difference between them, since the ADT and its implementation are the same code
    • The ADT is always a file, while an implementation is always a class in an object model

13. A language does not provide a built-in stack. Which is the best approach to use one?

    • Store the stack in a text file only, reading and writing each item as a new line of the file
    • Use a constant string as a stack, adding characters to the end of the text as each item is pushed
    • Implement a stack using an array or list with push and pop operations
    • Declare a single integer and call it a stack, which holds one value that the program updates

14. Which description best fits a graph as an ADT?

    • A fixed block of memory storing only numbers
    • Vertices connected by edges that represent relationships
    • A line of items accessed in first-in, first-out order
    • A set of key-value pairs with unique keys

15. A program stores the items in a shopping list in the order they were entered and removes the first item bought. Which ADT suits this?

    • Queue
    • Tree
    • Stack
    • Hash table

16. Why is a hash table a good ADT for finding a value by its key quickly?

    • It stores every value in a list and searches each one
    • It removes the need for keys entirely
    • A hash function maps each key directly to a storage location
    • It keeps values sorted in a binary file

17. Which statement compares a dynamic structure and a static one correctly?

    • Static structures can change size at runtime, while dynamic ones cannot
    • Both structures have the same memory behaviour
    • Dynamic structures are only used in binary files
    • Dynamic structures change size at runtime, while static structures have a fixed size

18. A data structure must store an unknown number of items that change frequently. Which kind is most suitable?

    • Fixed-length array
    • Static
    • Dynamic
    • Constant

19. Which ADT uses a parent-child structure with a single root node?

    • Queue
    • Stack
    • Dictionary
    • Tree

20. What is the purpose of the operations defined in an ADT?

    • To define the file format on disk, so that the data is stored in the same layout every time
    • To make all data public and global, so that every part of the program can read and write it
    • To specify how the data can be created, changed and accessed, regardless of implementation
    • To replace all variables in a program, so that data is held only inside the operation calls

Related quizzes

• Single- and multi-dimensional arrays Quiz · 4.2.1.2 · 20 questions
• Reading and writing text and binary files Quiz · 4.2.1.3 · 20 questions
• Linear, circular and priority queues Quiz · 4.2.2.1 · 20 questions
• Stack operations Quiz · 4.2.3.1 · 20 questions
• Graphs: weighted, directed and adjacency representations Quiz · 4.2.4.1 · 20 questions
• Trees and binary trees Quiz · 4.2.5.1 · 20 questions
• Hash tables, hashing and collisions Quiz · 4.2.6.1 · 20 questions
• Dictionaries and key-value pairs Quiz · 4.2.7.1 · 20 questions
• Vectors and vector operations Quiz · 4.2.8.1 · 20 questions
• Data types Quiz · 4.1.1.1 · 20 questions