H446 Revision

Quiz

1.4.2 Data structures

  1. Which structure is immutable?

    1. Tuple
    2. List
    3. Array
    4. Stack
    Show answer

    Answer: Tuple

    A tuple's items cannot be changed, added or removed after it has been created. Lists, arrays and stacks are mutable: their contents can change.

  2. Which statement about arrays is true?

    1. An array's size is fixed when it is created
    2. An array can hold items of different data types
    3. An array grows when an item is added to the end
    4. An array's first index is always 1
    Show answer

    Answer: An array's size is fixed when it is created

    An array is a static structure: its size is set when it is declared. Its elements all have the same type and, in OCR pseudocode, its indexes start at 0. A list is the structure that can grow and hold mixed types.

  3. Items 4, 9 and 2 are pushed onto an empty stack in that order. Then pop() is called twice. Which item is left on the stack?

    1. 4
    2. 2
    3. 9
    4. None, the stack is empty
    Show answer

    Answer: 4

    A stack is last in, first out. The first pop returns 2 (the last item pushed) and the second returns 9, leaving 4, which was pushed first.

  4. A circular queue is stored in an array with maxSize 6 (positions 0 to 5). The rear pointer is 5. Where does the next item go?

    1. Position 0
    2. Position 6
    3. Nowhere: the queue must be full
    4. Position 5, replacing the rear item
    Show answer

    Answer: Position 0

    The new rear is (5 + 1) MOD 6, which is 0, so the pointer wraps round to the start of the array. The queue is only full if all 6 spaces hold items, which the rear pointer alone does not tell you.

  5. Why is inserting an item into the middle of a linked list quicker than inserting it into the middle of an array?

    1. Only pointers change; no items have to move
    2. A linked list keeps its items next to each other in memory
    3. A linked list can be searched with a binary search
    4. Linked lists are static, so the space is already set aside
    Show answer

    Answer: Only pointers change; no items have to move

    To insert into a linked list you store the item in a free node and change two pointers. In an array, every item after the insertion point must move along one place.

  6. Which data structure would be best for an undo feature, which reverses the most recent action first?

    1. A stack
    2. A queue
    3. A hash table
    4. A tuple
    Show answer

    Answer: A stack

    Undo needs the most recent action first: last in, first out, which is how a stack works. A queue would undo the oldest action first.

  7. The values 40, 25, 60, 30 and 10 are added in that order to an empty binary search tree. Where does 30 go?

    1. Right child of 25
    2. Left child of 25
    3. Left child of 60
    4. Right child of 40
    Show answer

    Answer: Right child of 25

    Start at the root, 40. 30 is smaller, so go left to 25. 30 is larger than 25, so it becomes 25's right child.

  8. Which traversal of a binary search tree outputs its items in ascending order?

    1. In-order
    2. Pre-order
    3. Post-order
    4. Breadth-first
    Show answer

    Answer: In-order

    In-order visits the left subtree, then the node, then the right subtree. In a binary search tree everything on the left is smaller and everything on the right is larger, so the items come out sorted.

  9. In a binary search tree, a node with two children is removed. Which value can replace it?

    1. The smallest value in its right subtree
    2. Its left child, always
    3. The root of the tree
    4. The largest value in its right subtree
    Show answer

    Answer: The smallest value in its right subtree

    The smallest value in the right subtree is the node's in-order successor: it is larger than everything on the left and smaller than everything else on the right, so putting it in the gap keeps the tree in order. (The largest value in the left subtree would also work.) The largest value in the right subtree would be bigger than the rest of that subtree, breaking the rule.

  10. A graph has 1000 vertices but each vertex is joined to only 3 others. Which way of storing it uses less memory?

    1. An adjacency list
    2. An adjacency matrix
    3. Both use the same
    4. A 1D array of the vertices
    Show answer

    Answer: An adjacency list

    The graph is sparse. An adjacency matrix needs 1000 × 1000 cells whether or not edges exist, while an adjacency list stores only the 3 edges of each vertex.

  11. A hash table has 11 spaces and the hashing function key MOD 11. Space 3 already holds an item, and space 4 is empty. Using linear probing, where is the key 25 stored?

    1. Space 4
    2. Space 3
    3. Space 2
    4. Space 25
    Show answer

    Answer: Space 4

    25 MOD 11 is 3, but space 3 is taken: a collision. Linear probing puts the item in the next free space, which is 4.

  12. Which structure is used to keep track of vertices still to visit in a breadth-first traversal of a graph?

    1. A queue
    2. A stack
    3. A binary search tree
    4. A hash table
    Show answer

    Answer: A queue

    Breadth-first visits vertices in the order they were discovered, nearest first, which is first in, first out: a queue. A depth-first traversal uses a stack.