Data structures worksheet with answers

In a singly linked list, what does the next pointer of the last node contain?

1. ANull (no node)
2. BThe number of nodes in the list
3. CThe address of the first node
4. DThe address of the previous node

What is a deque (double-ended queue)?

1. AA queue sorted by priority
2. BTwo separate queues sharing one array
3. CA queue that only allows removal at the back
4. DA structure that allows insertion and removal at both ends

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

1. APush
2. BPeek
3. CEnqueue
4. DPop

An adjacency matrix for a graph with V vertices uses how much memory?

1. AO(V²)
2. BO(V + E)
3. CO(log V)
4. DO(E)

A hash table of size 7 uses h(k) = k mod 7 and linear probing. After inserting 10, where is 17 stored?

1. AIndex 3
2. BIndex 6
3. CIndex 4
4. DIndex 0

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 sorted array
2. BA singly linked list
3. CA doubly linked list
4. DA dynamic array

Kahn's algorithm for topological sorting repeatedly removes vertices with in-degree 0. Which structure holds those vertices?

1. AA max-heap ordered by out-degree
2. BAn adjacency matrix recording which vertices have already been removed
3. CA stack of all visited edges
4. DA queue (or any collection) of vertices whose in-degree is 0

How does a radix tree (compressed trie) improve on a plain trie?

1. AIt stores each word in a hash table at the root instead of in separate nodes
2. BIt keeps only the first letter of each word
3. CIt sorts the children of each node by frequency
4. DIt merges chains of single-child nodes into one edge labelled with a string