Data structures worksheet with answers

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

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

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

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

A hash table stores data as:

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

An adjacency matrix for a graph with V vertices uses how much memory?

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

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

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

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

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

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most n / 2
2. BThe height is exactly log₂ n
3. CThe height is at most log₂ n + 1
4. DThe height is at most 2 log₂(n + 1)

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

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