Data structures worksheet with answers

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

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

What is the name of the stack operation that adds an element to the top?

1. APeek
2. BEnqueue
3. CPop
4. DPush

What does a map (dictionary) store?

1. APairs of equal keys
2. BKey-value pairs with unique keys
3. COnly values in insertion order
4. DValues sorted by size

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. Ai + 1
2. B(i − 1) mod n
3. C2i + 1
4. D(i + 1) mod n

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. CPlace it at the root and sift it down
4. DRebuild the whole heap from scratch

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

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

Without union by rank or path compression, what is the worst-case cost of a single find in a union-find structure with n elements?

1. AO(α(n))
2. BO(log n)
3. CO(1)
4. DO(n)

Why might a server choose its hash function at random from a universal family?

1. ATo remove the need to resize the table
2. BTo make it very unlikely that an attacker can pick many keys that all collide
3. CTo make the hash table sorted
4. DTo guarantee that no two keys can ever collide, whatever keys an attacker sends