Data structures worksheet with answers

A hash table stores data as:

1. AKey–value pairs located by a hash function
2. BA fixed-length string
3. CA sorted list only
4. DA tree with ordered keys

Which structure is typically used to implement a priority queue?

1. AA stack
2. BA string
3. CA heap
4. DA singly linked list without order

In a graph, what is a cycle?

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

A trie (prefix tree) is especially efficient for:

1. ASorting numbers
2. BFinding shortest paths
3. CPrefix searches such as autocomplete
4. DStoring matrices

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

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

Which collision resolution method stores colliding keys in a list at the same bucket?

1. ADouble hashing
2. BLinear probing
3. CQuadratic probing
4. DSeparate chaining

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A80
2. B70
3. C40
4. D60

Which data structure supports an LRU (least recently used) cache with O(1) get and put?

1. AA binary search tree only
2. BA stack only
3. CA hash map combined with a doubly linked list
4. DA single sorted array