Data structures worksheet with answers

In a binary search tree, values in the left subtree of a node are:

1. ASmaller than the node's value
2. BEqual to the node's value
3. CLarger than the node's value
4. DIn random order

What is the max-heap property?

1. AAll leaves contain the maximum key
2. BEvery left child's key is greater than or equal to its right sibling's key
3. CEvery parent's key is greater than or equal to its children's keys
4. DThe keys are sorted from left to right

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

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

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA FIFO queue
2. BA min-priority queue
3. CA stack
4. DA set with no ordering

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

Which data structure does a running program use to keep track of active function calls and their local variables?

1. AA binary search tree of frames
2. BThe heap memory queue
3. CA hash table of functions
4. DThe call stack

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

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

What are the time and extra space costs of reversing a singly linked list in place?

1. AO(n) time and O(1) extra space
2. BO(1) time and O(1) extra space
3. CO(n log n) time and O(1) extra space
4. DO(n) time and O(n) extra space