Data structures worksheet with answers

Which operation is slow in an array but fast at the head of a linked list?

1. AAccessing the 5th element
2. BReading the last element by index
3. CFinding the length of a fixed array
4. DInserting at the beginning

A graph consists of:

1. AOnly a root and leaves
2. BRows and columns
3. CKeys and hashes only
4. DVertices (nodes) connected by edges

What is the root of a tree?

1. AThe node with the largest value
2. BThe top node with no parent
3. CA node with no children
4. DAny node in the middle

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the postorder traversal?

1. A4 5 2 3 1
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 2 5 1 3

A hash table of size 7 uses h(k) = k mod 7 and linear probing. After inserting 10, where is 17 stored?

1. AIndex 0
2. BIndex 3
3. CIndex 4
4. DIndex 6

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

1. ARemove the last element of the array
2. BMove the last element to the root and sift it down
3. CSearch all leaves for the new minimum
4. DRemove the root and shift all elements one place left

What does a splay tree do after each access?

1. ARecolours the nodes on the search path
2. BRotates the accessed node up to the root
3. CMoves the accessed node to a leaf
4. DRebuilds the whole tree in balanced form

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 sorted array of all n values
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 max-heap of size k, replacing its root when a smaller value arrives