Practice answers and guidance

Try each question before opening this section. Programming and design questions may have several valid solutions; the guidance below states the properties a correct answer must preserve.

Chapter 1

1. A queue specifies FIFO behaviour and operations. C has no built-in queue type; arrays or linked nodes can implement it.
2. Counter values are 0, 1, 2, 2, 3; result 3.
3. Require n > 0, or return a failure status for an empty array. On success, return a value at least as large as every element and equal to one of them.
4. For example: positive integer identifier, a null-terminated title within a fixed buffer, and a nonnegative finite price. Choose precision and currency handling to suit the application.

Chapter 2

1. 6 × 5 / 2 = 15 comparisons.
2. First-element match: Θ(1); absent key or match at the last position: Θ(n).
3. After k divisions the value is about n/2^k; reaching zero requires Θ(log n) iterations for positive n, accounting for integer division.
4. The predecessor must first be found. Traversing to position k can take Θ(k), even though relinking there is constant time.

Chapter 3

1. Move 18 to index 1, 7 to index 2 and 45 to index 3. Decrease length from 5 to 4: {23,18,7,45}.
2. The array has eight real, zero-initialised elements. A separate logical length of zero says that the application currently considers none of its slots occupied.
3. Offset = (2 × 5 + 3) × 8 = 104; address = 2104.
4. Verify length, order and returned status. A full insertion must fail without modifying any existing element or length; appending uses position n.

Chapter 4

1. For 6: compare 23, 12, 7; the interval becomes empty. For 60: compare 23 then 60, found at index 5.
2. lo and hi are both zero, so no array access occurs and the result is not found.
3. In {3,1,2}, searching for 3 can discard its actual location because midpoint comparisons no longer justify excluding either half.
4. Keep [lo,hi). If a[mid] < key, set lo = mid + 1; otherwise set hi = mid. At termination lo is the lower-bound position. A match exists if lo < n and a[lo] == key.

Chapter 5

1. {1,5,4,2} → {1,4,5,2} → {1,4,2,5}.
2. An earlier equal key is not shifted past the new equal key, preserving their original order.
3. {1,2,5-left,5-right,8,9} when the merge chooses the left half on equality.
4. Depending on whether the partition uses < or ≤, all equals collect on one side, repeatedly leaving a partition of size n − 1. A three-way partition groups values less than, equal to and greater than the pivot.
5. Sorted input makes zero shifts in the standard implementation. Reverse-sorted distinct input makes 1 + 2 + … + (n − 1) = n(n − 1)/2 shifts.

Chapter 6

1. 8 − 3 = 5; 5 × 2 = 10. Reversing operands would incorrectly compute 3 − 8.
2. Occupied slots are 3 and 0; next insertion is (3 + 2) mod 4 = 1.
3. A deque supports both ends, such as a work queue that accepts urgent work at the front. A priority queue removes according to a priority key, such as the next event by time.
4. Fill the ring, reject one additional item, dequeue once, enqueue again and verify FIFO order. Remove the final item, reject another dequeue and verify the unchanged empty state.
5. A B + C * D -.

Chapter 7

1. Null denotes no target. Dangling means a formerly referenced object's lifetime has ended. Neither may be dereferenced.
2. sizeof p is the size of the pointer itself. sizeof *p is the size of the pointed-to object.
3. Save old head; advance head to old head's next; free old. The second node becomes the sole node.
4. Ownership is of an allocation, not a pointer variable. The first free ends that allocation's lifetime; another free is invalid regardless of which alias is used.

Chapter 8

1. Allocate node 5, set its next to node 10, then set head to node 5. Existing nodes' links need not change.
2. After each iteration: (previous,current) is (10,20), (20,30), (30,NULL). Following saves the old successor before each reversal. Final head is 30, followed by 20 and 10.
3. Empty: tail is NULL. Singleton: tail is the sole node and tail->next == tail.
4. Both next and prev relationships must remain consistent, as must head and tail at boundaries.
5. Advance through both lists in exponent order. Copy the higher-exponent term, or sum coefficients when exponents match and advance both. Append the remaining terms, omitting zero coefficients under that policy.

Chapter 9

1. Stack top-to-bottom: 4 → 7 → NULL.
2. Without a rear reference, finding the last node takes a traversal. An alternative circular representation with a tail pointer would change the retained state.
3. Reading old->next after free(old) is a use-after-free.
4. Repeatedly detach and free front until NULL; set rear to NULL. Both endpoints must be NULL at completion.

Chapter 10

1. Preorder: 8,3,6,10. Inorder: 3,6,8,10. Postorder: 6,3,10,8.
2. A right-going chain with edge-count height 3.
3. Replace root key 40 with successor 50; remove the former leaf 50 from the left of 60. New inorder is 10,20,30,50,60,70.
4. Children are released before their parent, so their links remain accessible until no longer needed.
5. A root with two children, where only its right child has two children. Every internal node has two children, but the last level is not left-filled.

Chapter 11

1. Traversal must distinguish an actual subtree from a successor/predecessor link to avoid treating a thread as a child.
2. Minimum 2 keys; maximum 5 keys.
3. Insert 50 into right leaf [30,40], obtaining [30,40,50]. Before inserting 60, split it: root becomes [20,40], with children [10], [30], [50]. Insert 60 into the last child to obtain [50,60].
4. The root is the unique entry point and may have only two children while still allowing all leaves to share one depth. A separate root rule permits growth and shrinkage without violating non-root occupancy.

Chapter 12

1. No. Vertex 5 is unreachable from 0; a full graph traversal must start again there.
2. Rows 0–4 are 0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 1; 0 1 1 0 0; 0 0 1 0 0.
3. BFS minimises edge count. Two low-weight edges can cost less than one high-weight edge, so edge count need not minimise total weight.
4. They optimise different objectives: distances from a fixed source versus the total weight of a connecting tree. In a triangle with AB = 2, AC = 2 and BC = 1, a shortest-path tree from A uses AB and AC (total 4), whereas an MST uses BC plus one weight-2 edge (total 3).
5. It prevents accepting an edge whose endpoints are already connected, which would create a cycle.

Chapter 13

1. The mode requests truncation as part of opening an existing file, even if no later write occurs.
2. The loop can process a stale or incomplete record after a failed read. Check the conversion/read result before processing.
3. The address belongs to one process's memory layout and is not a stable identifier in a later process. Persist keys or validated file offsets instead.
4. For numeric records, one roll number and mark per line is sufficient for a simple format. Reject missing fields, extra unexpected fields, invalid numbers and out-of-range marks according to the declared grammar.

Chapter 14

1. RL: rotate right at node 30, then left at node 10, leaving root 20.
2. Repair can reduce a subtree's height, changing its parent's balance and propagating upwards.
3. Union {1,2,4,6,7}; intersection {4}; A − B {2,6}; B − A {1,7}.
4. AVL guarantees logarithmic height after every valid update. A standard skip list has logarithmic expected search but can have linear worst-case search for an unfavourable random structure.
5. Advance the pointer with the smaller value; it cannot match the larger current value or any later value in the other sorted list. On equality, emit once and advance both.

Appendix A

1. All start at slot 1 and occupy slots 1, 2 and 3 respectively.
2. A tombstone means an earlier probe chain may continue past the slot. Never-used means no insertion on that probe path has passed it under the usual linear-probing invariant.
3. Hash placement follows the hash/probe policy rather than key order. Collect and sort the keys, or use an ordered structure.

Appendix B

1. One inversion: the pair (3,2).
2. Equal values would be counted even though the inversion definition requires a strict decrease.