Data structures worksheet with answers

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

1. AHash table
2. BStack
3. CQueue
4. DLinked list

What does the peek (or top) operation on a stack do?

1. AReturns the top element without removing it
2. BRemoves the top element and returns it
3. CRemoves all elements from the stack
4. DReturns the bottom element of the stack

What does a hash function do in a hash table?

1. ASorts the keys in the table
2. BCounts how many keys are stored
3. CMaps a key to an index in the table
4. DEncrypts the values in the table

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 + 1 and i + 2
2. B2i + 1 and 2i + 2
3. C2i and 2i + 1
4. Di/2 and i/2 + 1

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

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

How is a new element inserted into a binary heap?

1. AInsert it at its sorted position by shifting all of the larger elements one place right
2. BPlace it at the end of the array and sift it up while it violates the heap property
3. CRebuild the whole heap from scratch
4. DPlace it at the root and sift it down

What does a splay tree do after each access?

1. ARecolours the nodes on the search path
2. BMoves the accessed node to a leaf
3. CRotates the accessed node up to the root
4. DRebuilds the whole tree in balanced form

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most log₂ n + 1
2. BThe height is at most 2 log₂(n + 1)
3. CThe height is at most n / 2
4. DThe height is exactly log₂ n