ITPEC FE Morning April 2020 Question 5
A list is implemented with two arrays box and next. Each element in the list corresponds to a pair (box[i], next[i]), where box[i] is the value of the element, and next[i] is the index to the next element in the list. When the element of value "H" is inserted between the third and fourth elements in the list shown below, which of the following is the value contained in next[8]? Here, next[0] contains the index of the leading (first) element of the list, the index i whose next[i] is 0 indicates the last element of the list, and each index i whose next[i] is blank indicates that the element is out of the list.
Explanation
7 — H goes after C, the third element, so it must point to G, the fourth element, stored at index 7.
Follow the chain from the head pointer, not the array order:
- •
next[0]= 1 → A at index 1 - •
next[1]= 5 → E at index 5 - •
next[5]= 3 → C at index 3 - •
next[3]= 7 → G at index 7 - •
next[7]= 2 → B at index 2, andnext[2]= 0 ends the list
The list is A, E, C, G, B, and H sits unused at index 8. To insert H between C and G, set next[8] to 7 (H → G), then set next[3] to 8 (C → H).
Answer (c)
Why not others:
- •(a) 3 — the index of C, H's predecessor; C's pointer is the one changed to 8, and pointing H back at C would make the loop C → H → C
- •(b) 5 — the index of E, the second element; H would point there only if it were inserted between A and E
- •(d) 8 — H's own index, which is the new value of
next[3];next[8]holding 8 would make H point to itself
Key rule: To insert X after P in a linked list, first copy P's old successor into X's pointer, then point P at X; positions come from walking the chain, not from the array index.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.