Data structures worksheet with answers

Which data structure is used to perform a level-order traversal of a tree?

1. AHash table
2. BQueue
3. CPriority queue
4. DStack

In a singly linked list, what does the next pointer of the last node contain?

1. AThe address of the first node
2. BThe address of the previous node
3. CThe number of nodes in the list
4. DNull (no node)

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

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

Why can a binary heap be stored in an array without any pointers?

1. AAll keys in a heap are equal
2. BArrays automatically keep the keys in sorted order, so no pointers are needed
3. CIt is a complete binary tree, so positions follow simple index formulas
4. DHeaps never contain more than 100 elements

Which data structure is used by depth-first search (iterative version)?

1. AA stack
2. BA queue
3. CA hash table only
4. DA heap

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index ⌊(i − 1) / 2⌋
2. BAt index i − 1
3. CAt index 2i + 1
4. DAt index ⌊i / 2⌋ + 1

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

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

Which pair of traversals always determines a unique binary tree with distinct keys?

1. APreorder and inorder
2. BLevel-order alone
3. CPreorder alone
4. DPreorder and postorder