Data structures worksheet with answers

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

1. ABinary tree
2. BHeap
3. CQueue
4. DStack

What does a map (dictionary) store?

1. AKey-value pairs with unique keys
2. BValues sorted by size
3. COnly values in insertion order
4. DPairs of equal keys

In a singly linked list, what does the next pointer of the last node contain?

1. ANull (no node)
2. BThe address of the first node
3. CThe address of the previous node
4. DThe number of nodes in the list

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

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

An adjacency matrix for a graph with V vertices uses how much memory?

1. AO(log V)
2. BO(V + E)
3. CO(V²)
4. DO(E)

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

What is the main advantage of a skip list over a sorted linked list?

1. AExpected O(log n) search by using several levels of forward pointers
2. BGuaranteed O(1) search because every node stores a pointer to every other node
3. CIt uses no extra memory
4. DIt stores keys without order

Which structure lets you compute the maximum of every window of size k in an array in O(n) total?

1. AA min-heap rebuilt for every window
2. BA sorted array updated by shifting
3. CA singly linked list of the window's elements
4. DA deque holding indices in decreasing order of value