Data structures worksheet with answers

Which structure is typically used to implement a priority queue?

1. AA stack
2. BA heap
3. CA singly linked list without order
4. DA string

What is a directed graph?

1. AA graph whose edges all have weights
2. BA graph whose edges have a direction from one vertex to another
3. CA graph that has no cycles
4. DA graph in which every pair of distinct vertices is joined by an edge

What is the root of a tree?

1. AThe top node with no parent
2. BAny node in the middle
3. CA node with no children
4. DThe node with the largest value

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. C(i − 1) mod n
4. D2i + 1

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

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

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

Which statement about heapsort is correct?

1. AIt is stable and needs O(n) extra memory
2. BIt sorts in place in O(n log n) worst-case time but is not stable
3. CIt runs in O(n) time on any input
4. DIt needs a binary search tree as extra storage, so it uses O(n) extra memory

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. AInserting elements at any position
2. BSorting the array and binary search
3. CFinding the median in O(1)
4. DPrefix-sum queries and single-element updates