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 any leaf, which must be searched
4. DIn the last array position

What is the load factor of a hash table?

1. AThe number of stored elements divided by the number of buckets
2. BThe number of collisions so far
3. CThe number of buckets divided by the average length of the keys stored
4. DThe time needed to load the table from disk

In a tree, what are sibling nodes?

1. ANodes that have no children
2. BNodes that share the same parent
3. CNodes at the same depth in different subtrees
4. DA node and its parent

Which collision resolution method stores colliding keys in a list at the same bucket?

1. ASeparate chaining
2. BDouble hashing
3. CLinear probing
4. DQuadratic probing

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. Ai/2 and i/2 + 1
2. Bi + 1 and i + 2
3. C2i + 1 and 2i + 2
4. D2i and 2i + 1

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

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

In a hash table using open addressing, why is deletion often done with a "tombstone" marker?

1. ADeleted keys must be kept forever for security, so slots can never be reused
2. BTombstones speed up hashing
3. CIt makes the table sorted
4. DEmptying the slot could break the probe sequence for other keys

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