Data Structures Practice Exam — Free

Sift-up compares the new key with its parent at index $\lfloor (i-1)/2 \rfloor$ and swaps while the key is larger than the parent.

• Insert 12: [12].
• Insert 7 at index 1; parent 12 is larger, stop: [12, 7].
• Insert 20 at index 2; parent 12 is smaller, swap: [20, 7, 12].
• Insert 3 at index 3; parent (index 1) is 7, larger, stop: [20, 7, 12, 3].
• Insert 25 at index 4; parent 7 is smaller, swap to index 1; parent 20 is smaller, swap to the root: [25, 20, 12, 3, 7].
• Insert 9 at index 5; parent (index 2) is 12, larger, stop: [25, 20, 12, 3, 7, 9].
• Insert 14 at index 6; parent 12 is smaller, swap to index 2; parent 25 is larger, stop: [25, 20, 14, 3, 7, 9, 12].

Verify the heap property on the result: 25 is at least 20 and 14; 20 is at least 3 and 7; 14 is at least 9 and 12. Every parent dominates its children and the array is a complete tree, so this is a valid max-heap.

Option B is the tempting one: it is what the linear-time bottom-up build-heap produces when applied to the whole array [12, 7, 20, 3, 25, 9, 14] at once. It is also a valid max-heap, but the question specifies repeated insertion, and the two procedures generally give different arrays. Option C is the keys in descending order, which sift-up never produces here (7 and 3 never move once placed). Option D is a min-heap.

[25, 20, 14, 3, 7, 9, 12] (option A).

Compute each home slot with $h(k) = k \bmod 11$ and probe forward from it until an empty slot appears.

• 23: $23\bmod 11 = 1$; slot 1 is empty, store there.
• 14: $14\bmod 11 = 3$; slot 3 is empty, store there.
• 34: $34\bmod 11 = 1$; slot 1 holds 23, so probe slot 2, which is empty: store at 2.
• 45: $45\bmod 11 = 1$; slots 1, 2 and 3 are occupied; slot 4 is empty: store at 4.
• 12: $12\bmod 11 = 1$; slots 1, 2, 3 and 4 are occupied; slot 5 is empty: store at 5.

Final table (slot: key): 1: 23, 2: 34, 3: 14, 4: 45, 5: 12, with all other slots empty.

A search for 12 retraces its insertion path: start at slot 1 and compare with 23, 34, 14 and 45, then find 12 at slot 5. That is 5 slots examined. Check by counting positions: slot 5 is 4 places past the home slot 1, so the probe count is $4+1 = 5$.

Four of the five keys hash to slot 1, which is why they form one contiguous run from slot 1 to slot 5. This is primary clustering, the main weakness of linear probing: the run grows and every key that lands in it pays for the whole run. The load factor is $5/11 \approx 0.45$, and an unsuccessful search for a key with home slot 1 (such as 56) would examine slots 1 through 6, six probes, before reaching an empty slot.

23 → 1, 14 → 3, 34 → 2, 45 → 4, 12 → 5; the search for 12 examines 5 slots.

Balance factor = height(left subtree) − height(right subtree); every node must have balance −1, 0 or 1, and rebalancing happens at the lowest unbalanced ancestor of the new node. In the balance checks below, heights count nodes (an empty subtree has height 0, a single node height 1); the differences are the same under the edge count used for part (b).

Insert 50, 30, 70: root 50 with children 30 and 70, balanced. Insert 20 (left of 30) and 40 (right of 30): node 50 has balance +1, still fine.

Insert 10 (left of 20). Node 50 now has left height 3 and right height 1, balance +2. The new key lies in the left subtree of 50's left child, a left-left case, so a single right rotation at 50 fixes it: 30 becomes the root, 50 becomes its right child, and 30's former right child 40 becomes 50's left child. Tree: 30 with children 20 (left child 10) and 50 (children 40, 70).

Insert 55: right of 30, right of 50, left of 70. Balances: 70 is +1, 50 is −1, 30 is −1. No rotation.

Insert 65: right of 55. Node 70 now has left height 2 and right height 0, balance +2. The new key is in the right subtree of 70's left child, a left-right case, so a double rotation is needed: a left rotation at 55 (65 moves up, 55 becomes its left child), then a right rotation at 70 (65 becomes the subtree root with children 55 and 70). Afterwards 50 has children 40 and 65 with balance −1, and the root 30 has balance −1.

Final tree: 30 has left child 20 (with left child 10) and right child 50; 50 has children 40 and 65; 65 has children 55 and 70. Preorder (node, left, right): 30, 20, 10, 50, 40, 65, 55, 70. The longest root-to-leaf path is 30–50–65–55 (or 30–50–65–70), 3 edges. Check: the in-order traversal 10, 20, 30, 40, 50, 55, 65, 70 is sorted, so the BST property holds, and every balance factor lies within −1 to 1.

(a) Single right rotation at 50 after inserting 10; double rotation (left at 55, then right at 70) after inserting 65. (b) Preorder 30, 20, 10, 50, 40, 65, 55, 70; height 3.