Data structures worksheet with answers

What defines a binary tree?

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

What does the peek (or top) operation on a stack do?

1. AReturns the top element without removing it
2. BRemoves the top element and returns it
3. CReturns the bottom element of the stack
4. DRemoves all elements from the stack

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

1. ALeft subtree, then right subtree, then node
2. BLeft subtree, then node, then right subtree
3. CRight subtree, then node, then left subtree
4. DNode, then left subtree, then right subtree

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

1. ABoth subtrees of every node contain exactly the same number of nodes
2. BThe heights of the left and right subtrees differ by at most 1
3. CAll leaves are at exactly the same depth
4. DEvery node is coloured red or black

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

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

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

1. AThere is no maximum
2. B2
3. C0.5
4. D1

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

Which structure lets you compute the maximum of every window of size k in an array in O(n) total?

1. AA deque holding indices in decreasing order of value
2. BA singly linked list of the window's elements
3. CA sorted array updated by shifting
4. DA min-heap rebuilt for every window