Data structures worksheet with answers

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

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

In a singly linked list, each node contains:

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

Which data structure is used to perform a level-order traversal of a tree?

1. AQueue
2. BStack
3. CPriority queue
4. DHash table

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. CA binary search tree of frames
4. DThe call stack

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

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

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

1. AIts main diagonal always contains ones
2. BEach row has exactly one 1
3. CIt is always upper triangular
4. DIt is symmetric about the main diagonal

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

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. BA queue (or any collection) of vertices whose in-degree is 0
3. CA stack of all visited edges
4. DAn adjacency matrix recording which vertices have already been removed