Data structures worksheet with answers

What is the max-heap property?

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

What is the defining feature of a set as an abstract data type?

1. AIt stores elements without duplicates
2. BIt stores elements in sorted order
3. CIt stores key-value pairs
4. DIt allows access only at one end

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

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

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

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 / 2⌋ + 1
3. CAt index 2i + 1
4. DAt index ⌊(i − 1) / 2⌋

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

The keys 5, 3, 8, 1 are inserted in this order into an empty array-based binary min-heap. What is the final array?

1. A[3, 1, 8, 5]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 5, 8]

In a circular buffer, front == rear can mean either empty or full. What is a common way to tell them apart?

1. AKeep a separate element count, or always leave one slot unused
2. BAlways clear the buffer whenever front equals rear, so the state is empty
3. CMake the buffer size a power of two
4. DStore the front and rear in the same variable