Data structures worksheet with answers

What is the name of the queue operation that removes the element at the front?

1. ADequeue
2. BInsert
3. CPush
4. DEnqueue

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

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

What is a directed graph?

1. AA graph in which every pair of distinct vertices is joined by an edge
2. BA graph whose edges all have weights
3. CA graph whose edges have a direction from one vertex to another
4. DA graph that has no cycles

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 singly linked list
4. DA sorted array

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

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

In a hash table using open addressing, what is the maximum possible load factor?

1. A1
2. B0.5
3. C2
4. DThere is no maximum

Which statement about heapsort is correct?

1. AIt needs a binary search tree as extra storage, so it uses O(n) extra memory
2. BIt is stable and needs O(n) extra memory
3. CIt sorts in place in O(n log n) worst-case time but is not stable
4. DIt runs in O(n) time on any input

Without union by rank or path compression, what is the worst-case cost of a single find in a union-find structure with n elements?

1. AO(α(n))
2. BO(1)
3. CO(n)
4. DO(log n)