Data structures worksheet with answers

Where is the smallest element of a binary min-heap found?

1. AAt the root
2. BIn the leftmost leaf
3. CIn the last array position
4. DIn any leaf, which must be searched

In a singly linked list, each node contains:

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

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

1. AHeap
2. BQueue
3. CBinary tree
4. DStack

What is the cost of inserting an element in the middle of an array of n elements?

1. AO(n²), because each element moves n times
2. BO(n), because later elements must shift
3. CO(log n), because of binary search
4. DO(1), because the index is known

Why can a binary heap be stored in an array without any pointers?

1. AAll keys in a heap are equal
2. BArrays automatically keep the keys in sorted order, so no pointers are needed
3. CIt is a complete binary tree, so positions follow simple index formulas
4. DHeaps never contain more than 100 elements

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

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

Which statement about heapsort is correct?

1. AIt is stable and needs O(n) extra memory
2. BIt sorts in place in O(n log n) worst-case time but is not stable
3. CIt runs in O(n) time on any input
4. DIt needs a binary search tree as extra storage, so it uses O(n) extra memory

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 single left rotation at the unbalanced node
2. BRecolouring the node and its child
3. CA single right rotation at the unbalanced node
4. DA left rotation at the child, then a right rotation at the node