Data structures worksheet with answers

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

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

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

1. ALinked list
2. BQueue
3. CStack
4. DHash table

The depth of a node in a tree is:

1. AThe number of edges from the root to that node
2. BThe number of edges from that node to the deepest leaf
3. CThe number of children of that node
4. DThe number of nodes in its subtree

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. CLinked lists always store elements on disk
4. DArrays use fewer instructions to compare values

An adjacency matrix for a graph with V vertices uses how much memory?

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

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index i − 1
2. BAt index ⌊(i − 1) / 2⌋
3. CAt index ⌊i / 2⌋ + 1
4. DAt index 2i + 1

How does a radix tree (compressed trie) improve on a plain trie?

1. AIt sorts the children of each node by frequency
2. BIt stores each word in a hash table at the root instead of in separate nodes
3. CIt merges chains of single-child nodes into one edge labelled with a string
4. DIt keeps only the first letter of each word

Which problem of linear probing does double hashing mainly reduce?

1. AThe need for a hash function
2. BThe O(n) cost of reading a key's value
3. CThe need to store keys in the table
4. DPrimary clustering, where long runs of occupied slots form