Data structures worksheet with answers

What is a directed graph?

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

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 collisions so far
3. CThe time needed to load the table from disk
4. DThe number of stored elements divided by the number of buckets

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

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

An in-order traversal of a binary search tree visits the keys in:

1. AAscending sorted order
2. BLevel order
3. CInsertion order
4. DDescending order always

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 sorted array
2. BA singly linked list
3. CA doubly linked list
4. DA dynamic array

What is the running time of breadth-first search on a graph with V vertices stored as an adjacency matrix?

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

Inserting a key into an AVL tree makes a node's left subtree too tall, and the new key went into the left subtree of its left child (left-left case). Which fix is applied?

1. AA left rotation at the child, then a right rotation at the node
2. BA single right rotation at the unbalanced node
3. CRecolouring the node and its child
4. DA single left rotation at the unbalanced node