Data structures worksheet with answers

In which order does a postorder traversal of a binary tree visit nodes?

1. ALeft subtree, then right subtree, then node
2. BRight subtree, then node, then left subtree
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then node, then right subtree

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

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

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

1. AFinding the length of a fixed array
2. BInserting at the beginning
3. CAccessing the 5th element
4. DReading the last element by index

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

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

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

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

1. A1
2. Bn (it becomes a linked list)
3. C√n
4. Dlog₂ n

Which statement about heapsort is correct?

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

A dynamic array doubles when full. Why do many implementations shrink it only when it is one quarter full, not half full?

1. ABecause the memory allocator can only release memory in quarters of a block
2. BBecause halving at one half would lose elements
3. CTo avoid repeated resizing when pushes and pops alternate near the boundary
4. DTo keep the array sorted