Data structures worksheet with answers

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

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

In a singly linked list, each node contains:

1. AData and references to all other nodes
2. BData and an index
3. CData and a reference to the next node
4. DOnly data

What is a directed graph?

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

What is the time complexity of searching for a key in a balanced binary search tree?

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

The keys 50, 30, 70, 20, 40 are inserted in this order into an empty binary search tree. What is the left child of 30?

1. A40
2. B50
3. C70
4. D20

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AA stack
2. BA hash table
3. CAn unsorted linked list
4. DA balanced binary search tree

How long does it take to search for an arbitrary key in a binary min-heap of n elements?

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

For a hash table to work correctly, which rule must hash and equality follow?

1. ADifferent keys must have different hash values
2. BEqual keys must have equal hash values
3. CHash values must be prime numbers
4. DEqual hash values imply equal keys