Data structures worksheet with answers

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

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

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. CAn edge with a weight of zero
4. DA path that visits every vertex

What is the load factor of a hash table?

1. AThe number of buckets divided by the average length of the keys stored
2. BThe number of stored elements divided by the number of buckets
3. CThe number of collisions so far
4. DThe time needed to load the table from disk

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A2i + 1
2. B(i − 1) mod n
3. Ci + 1
4. D(i + 1) mod n

You have a reference to a node in the middle of a list. In which list can you remove it in O(1)?

1. AA dynamic array
2. BA doubly linked list
3. CA sorted array
4. DA singly linked list

AVL trees and red-black trees guarantee:

1. AThat keys are stored in insertion order
2. BO(log n) height through rebalancing
3. CThat no node has two children
4. DConstant-time search in every case

The keys 5, 3, 8, 1 are inserted in this order into an empty array-based binary min-heap. What is the final array?

1. A[3, 1, 8, 5]
2. B[1, 3, 5, 8]
3. C[1, 5, 8, 3]
4. D[1, 3, 8, 5]

What are the time and extra space costs of reversing a singly linked list in place?

1. AO(n log n) time and O(1) extra space
2. BO(1) time and O(1) extra space
3. CO(n) time and O(n) extra space
4. DO(n) time and O(1) extra space