Data structures worksheet with answers

In an undirected graph, what is the degree of a vertex?

1. AThe length of the longest path from it
2. BIts position in the adjacency list
3. CThe number of edges connected to it
4. DThe number of vertices in the graph

In a graph, what is a cycle?

1. AA vertex with no edges
2. BA path that visits every vertex
3. CA path that starts and ends at the same vertex
4. DAn edge with a weight of zero

What does a hash function do in a hash table?

1. ACounts how many keys are stored
2. BEncrypts the values in the table
3. CMaps a key to an index in the table
4. DSorts the keys in the table

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

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

The keys 50, 30, 70, 20, 40 are inserted in this order into an empty binary search tree. What is the left child of 30?

1. A70
2. B50
3. C20
4. D40

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA stack
2. BA min-priority queue
3. CA set with no ordering
4. DA FIFO queue

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. APrefix-sum queries and single-element updates
2. BFinding the median in O(1)
3. CSorting the array and binary search
4. DInserting elements at any position

You must keep the k smallest values from a stream of n numbers using O(k) memory. Which approach works in O(n log k) time?

1. AA min-heap holding all n values, from which the k smallest are popped at the end
2. BA FIFO queue of the last k values
3. CA max-heap of size k, replacing its root when a smaller value arrives
4. DA sorted array of all n values