Data structures worksheet with answers

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

1. AGraph
2. BHash set
3. CStack
4. DQueue

In a singly linked list, each node contains:

1. AOnly data
2. BData and an index
3. CData and a reference to the next node
4. DData and references to all other nodes

What is the name of the stack operation that adds an element to the top?

1. APush
2. BPeek
3. CEnqueue
4. DPop

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. Alog₂ n
2. B√n
3. Cn (it becomes a linked list)
4. D1

What balance condition does an AVL tree maintain at every node?

1. AAll leaves are at exactly the same depth
2. BEvery node is coloured red or black
3. CThe heights of the left and right subtrees differ by at most 1
4. DBoth subtrees of every node contain exactly the same number of nodes

AVL trees and red-black trees guarantee:

1. AThat no node has two children
2. BO(log n) height through rebalancing
3. CConstant-time search in every case
4. DThat keys are stored in insertion order

Why are B-trees used in databases and file systems?

1. AThey need no rebalancing
2. BThey store data unsorted
3. CTheir high branching factor keeps the tree shallow, reducing slow disk reads
4. DThey use less memory than any array, so the entire index always fits in main memory

You must keep the k smallest values from a stream of n numbers using O(k) memory. Which approach works in O(n log k) time?

1. AA max-heap of size k, replacing its root when a smaller value arrives
2. BA FIFO queue of the last k values
3. CA min-heap holding all n values, from which the k smallest are popped at the end
4. DA sorted array of all n values