Data structures worksheet with answers

What does each node in a doubly linked list contain?

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

How many edges does a tree with n nodes have?

1. An + 1
2. Bn − 1
3. Cn
4. D2n

What is the root of a tree?

1. AAny node in the middle
2. BA node with no children
3. CThe top node with no parent
4. DThe node with the largest value

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the postorder traversal?

1. A5 4 3 2 1
2. B4 5 2 3 1
3. C1 2 4 5 3
4. D4 2 5 1 3

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(log n)
2. BO(n)
3. CO(1)
4. DO(n²)

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

1. A0.5
2. BThere is no maximum
3. C1
4. D2

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 single right rotation at the unbalanced node
2. BA single left rotation at the unbalanced node
3. CRecolouring the node and its child
4. DA left rotation at the child, then a right rotation at the node

In a circular buffer, front == rear can mean either empty or full. What is a common way to tell them apart?

1. AStore the front and rear in the same variable
2. BAlways clear the buffer whenever front equals rear, so the state is empty
3. CMake the buffer size a power of two
4. DKeep a separate element count, or always leave one slot unused