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 two pointers, one to the next node and one to the node after that
3. CData and a pointer to the next node only
4. DTwo copies of the data and one pointer

In which order does a preorder traversal of a binary tree visit nodes?

1. ALeft subtree, then right subtree, then node
2. BLeft subtree, then node, then right subtree
3. CLevel by level from the top
4. DNode, then left subtree, then right subtree

Which data structure works on the principle "first in, first out"?

1. ABinary tree
2. BStack
3. CQueue
4. DHeap

What is the cost of inserting an element in the middle of an array of n elements?

1. AO(log n), because of binary search
2. BO(n), because later elements must shift
3. CO(1), because the index is known
4. DO(n²), because each element moves n times

What balance condition does an AVL tree maintain at every node?

1. AThe heights of the left and right subtrees differ by at most 1
2. BEvery node is coloured red or black
3. CBoth subtrees of every node contain exactly the same number of nodes
4. DAll leaves are at exactly the same depth

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AA balanced binary search tree
2. BA hash table
3. CA stack
4. DAn unsorted linked list

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

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

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