Data structures worksheet with answers

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

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

What does a hash function do in a hash table?

1. AEncrypts the values in the table
2. BMaps a key to an index in the table
3. CCounts how many keys are stored
4. DSorts the keys in the table

In a tree, what is a leaf?

1. AA node with exactly one child
2. BA node with no parent
3. CA node with no children
4. DThe node with the largest value

A circular buffer (ring buffer) is commonly used to implement:

1. AA hash function
2. BA graph traversal
3. CA fixed-size queue
4. DA binary search tree

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

1. ALinear probing
2. BSeparate chaining
3. CQuadratic probing
4. DDouble hashing

How much memory does an adjacency list use for a graph with V vertices and E edges?

1. AO(V × E)
2. BO(E²)
3. CO(V²)
4. DO(V + E)

A segment tree is typically used to:

1. AStore a graph's edges
2. BImplement a stack
3. CAnswer range queries (such as range sums) and updates in O(log n)
4. DSort strings alphabetically by storing each prefix in a separate tree node

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AB+ trees use binary internal nodes, which reduces the number of disk reads
2. BB+ trees do not need to be balanced
3. CB+ trees store data only in the root
4. DAll records are in linked leaves, which makes range scans efficient