Data structures worksheet with answers

What does a map (dictionary) store?

1. APairs of equal keys
2. BOnly values in insertion order
3. CValues sorted by size
4. DKey-value pairs with unique keys

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

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

How many edges does a tree with n nodes have?

1. An
2. Bn − 1
3. Cn + 1
4. D2n

A node in a binary search tree has a right subtree. Where is its in-order successor?

1. AThe rightmost node of its left subtree
2. BIts parent, always
3. CIts right child, always
4. DThe leftmost node of its right subtree

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. ALinked lists always store elements on disk
2. BArray traversal is O(1) in total, while linked list traversal is O(n)
3. CArrays use fewer instructions to compare values
4. DArray elements are contiguous, so they make good use of the CPU cache

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

1. AAdjacency list
2. BA single sorted array of vertices
3. CA binary heap of edges
4. DAdjacency matrix

Why can elements not simply be deleted from a standard Bloom filter by clearing their bits?

1. ABloom filters store the full elements, and these cannot be located again once hashed
2. BBits in a Bloom filter cannot be changed after creation
3. CDeleting would increase the false positive rate to 100%
4. DThose bits may also belong to other elements, which would cause false negatives

In Kruskal's minimum spanning tree algorithm, what is the union-find structure used for?

1. AChecking whether an edge's two endpoints are already connected
2. BStoring each vertex's current distance from the source during the search
3. CSorting the edges by weight
4. DChoosing the starting vertex