Data structures worksheet with answers

What is the max-heap property?

1. AThe keys are sorted from left to right
2. BEvery parent's key is greater than or equal to its children's keys
3. CEvery left child's key is greater than or equal to its right sibling's key
4. DAll leaves contain the maximum key

The depth of a node in a tree is:

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

What does a hash function do in a hash table?

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

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

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

Which data structure is used by depth-first search (iterative version)?

1. AA queue
2. BA heap
3. CA hash table only
4. DA stack

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. Clog₂ n
4. D√n

What does a splay tree do after each access?

1. ARebuilds the whole tree in balanced form
2. BRecolours the nodes on the search path
3. CMoves the accessed node to a leaf
4. DRotates the accessed node up to the root

A segment tree is typically used to:

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