Data structures worksheet with answers

Which operation is slow in an array but fast at the head of a linked list?

1. AAccessing the 5th element
2. BReading the last element by index
3. CInserting at the beginning
4. DFinding the length of a fixed array

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

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

What is the name of the queue operation that removes the element at the front?

1. AEnqueue
2. BPush
3. CDequeue
4. DInsert

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. A2i + 1 and 2i + 2
2. B2i and 2i + 1
3. Ci + 1 and i + 2
4. Di/2 and i/2 + 1

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. CRemove the root and shift all elements one place left
4. DMove the last element to the root and sift it down

Why can a binary heap be stored in an array without any pointers?

1. AAll keys in a heap are equal
2. BArrays automatically keep the keys in sorted order, so no pointers are needed
3. CHeaps never contain more than 100 elements
4. DIt is a complete binary tree, so positions follow simple index formulas

Which data structure supports an LRU (least recently used) cache with O(1) get and put?

1. AA binary search tree only
2. BA hash map combined with a doubly linked list
3. CA single sorted array
4. DA stack only

For each element of an array you want the next greater element to its right, in O(n) total time. Which structure helps?

1. AA binary search tree rebuilt for each element
2. BA hash table of all elements
3. CA queue that holds every pair of elements
4. DA stack that keeps elements waiting for their answer