Data structures worksheet with answers

What is the root of a tree?

1. AThe node with the largest value
2. BThe top node with no parent
3. CAny node in the middle
4. DA node with no children

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 number of nodes in the list
4. DThe address of the previous node

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

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

A trie (prefix tree) is especially efficient for:

1. AStoring matrices
2. BPrefix searches such as autocomplete
3. CSorting numbers
4. DFinding shortest paths

What is true of the adjacency matrix of an undirected graph?

1. AIts main diagonal always contains ones
2. BIt is symmetric about the main diagonal
3. CIt is always upper triangular
4. DEach row has exactly one 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(n²)
4. DO(1)

Under simple uniform hashing, what is the expected time of a search in a hash table with chaining, n keys and m buckets?

1. AO(1 + α), where α = n / m
2. BO(m)
3. CO(n)
4. DO(log n)

Which statement about heapsort is correct?

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