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

What does each node in a doubly linked list contain?

1. AData and two pointers, one to the next node and one to the node after that
2. BTwo copies of the data and one pointer
3. CData and a pointer to the next node only
4. DData, a pointer to the next node and a pointer to the previous node

What defines a binary tree?

1. AEvery node has exactly two children
2. BEvery node stores a binary number
3. CEvery node has at most two children
4. DThe tree has exactly two levels

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. Ai + 1 and i + 2
2. B2i + 1 and 2i + 2
3. C2i and 2i + 1
4. Di/2 and i/2 + 1

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

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

1. AInsertion order
2. BLevel order
3. CAscending sorted order
4. DDescending order always

Why might a server choose its hash function at random from a universal family?

1. ATo make it very unlikely that an attacker can pick many keys that all collide
2. BTo make the hash table sorted
3. CTo remove the need to resize the table
4. DTo guarantee that no two keys can ever collide, whatever keys an attacker sends

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. A60
2. B80
3. C40
4. D70