Data structures worksheet with answers

Which data structure is most suitable for the "undo" feature in a text editor?

1. AStack
2. BHash set
3. CQueue
4. DGraph

Which data structure works on the principle "first in, first out"?

1. AQueue
2. BBinary tree
3. CHeap
4. DStack

What does a map (dictionary) store?

1. APairs of equal keys
2. BOnly values in insertion order
3. CKey-value pairs with unique keys
4. DValues sorted by size

How does extract-min work in a binary min-heap?

1. AMove the last element to the root and sift it down
2. BRemove the root and shift all elements one place left
3. CRemove the last element of the array
4. DSearch all leaves for the new minimum

What is the value of the postfix expression 3 4 + 2 * ?

1. A11
2. B10
3. C14
4. D24

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. AArray traversal is O(1) in total, while linked list traversal is O(n)
2. BArray elements are contiguous, so they make good use of the CPU cache
3. CArrays use fewer instructions to compare values
4. DLinked lists always store elements on disk

Inserting a key into an AVL tree makes a node's left subtree too tall, and the new key went into the left subtree of its left child (left-left case). Which fix is applied?

1. AA left rotation at the child, then a right rotation at the node
2. BA single right rotation at the unbalanced node
3. CRecolouring the node and its child
4. DA single left rotation at the unbalanced node

Which property keeps every B-tree perfectly balanced?

1. AEach node stores one key
2. BEvery node has exactly two children
3. CAll leaves are at the same depth
4. DThe keys are stored only in the root