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 all elements from the stack
3. CRemoves the top element and returns it
4. DReturns the top element without removing it

In an adjacency list representation of a graph, what is stored for each vertex?

1. AA row of V Boolean values
2. BThe shortest path to every other vertex
3. CThe total number of edges in the graph
4. DA list of its neighbouring vertices

What is the load factor of a hash table?

1. AThe number of collisions so far
2. BThe time needed to load the table from disk
3. CThe number of stored elements divided by the number of buckets
4. DThe number of buckets divided by the average length of the keys stored

How long does a search for a word of length L take in a trie with a fixed alphabet?

1. AO(n), where n is the number of words
2. BO(log n), where n is the number of words
3. CO(L), independent of how many words are stored
4. DO(L × n)

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D4 5 2 3 1

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

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(log n)
2. BO(n)
3. CO(m)
4. DO(1 + α), where α = n / m

What is the running time of breadth-first search on a graph with V vertices stored as an adjacency matrix?

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