Data structures worksheet with answers

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

1. APop
2. BPush
3. CEnqueue
4. DPeek

Which structure is typically used to implement a priority queue?

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

In a graph, what is a cycle?

1. AAn edge with a weight of zero
2. BA path that visits every vertex
3. CA path that starts and ends at the same vertex
4. DA vertex with no edges

You have a reference to a node in the middle of a list. In which list can you remove it in O(1)?

1. AA singly linked list
2. BA dynamic array
3. CA sorted array
4. DA doubly linked list

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

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

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

1. AThe heap memory queue
2. BA hash table of functions
3. CThe call stack
4. DA binary search tree of frames

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

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

You must keep the k smallest values from a stream of n numbers using O(k) memory. Which approach works in O(n log k) time?

1. AA max-heap of size k, replacing its root when a smaller value arrives
2. BA sorted array of all n values
3. CA min-heap holding all n values, from which the k smallest are popped at the end
4. DA FIFO queue of the last k values