Data structures worksheet with answers

What is the name of the stack operation that adds an element to the top?

1. APush
2. BPeek
3. CPop
4. DEnqueue

In a graph, what is a cycle?

1. AA path that starts and ends at the same vertex
2. BAn edge with a weight of zero
3. CA path that visits every vertex
4. DA vertex with no edges

In a hash table, what is a collision?

1. AThe table runs out of memory
2. BTwo different keys map to the same index
3. CTwo equal keys are stored twice
4. DA key cannot be hashed at all

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

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

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. AArray elements are contiguous, so they make good use of the CPU cache
2. BLinked lists always store elements on disk
3. CArrays use fewer instructions to compare values
4. DArray traversal is O(1) in total, while linked list traversal is O(n)

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

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 remove the need to resize the table
3. CTo make the hash table sorted
4. DTo make it very unlikely that an attacker can pick many keys that all collide

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