ITPEC FE Subject B October 2024 Question 10

Topic: Linked List

From the answer group below, select the correct answer to be inserted into blank in the program.

The procedure addNode adds a node to a singly-linked list at the position specified by the argument pos. The argument pos is a positive integer that is equal to or less than the (number of nodes + 1) in the list. The position at the top of the list is 1.
The class ListNode represents a node in a singly-linked list. The table summarizes an explanation of the member variables of the class ListNode. ListNode-type variables store references to instances of the class ListNode. A reference to the first node in the list is pre-stored in the global variable listHead.

Table Explanation of the member variables of the class ListNode

Member variableTypeDescription
valcharacterThe value of a node.
nextListNodeA reference for the next node.If no next node exists, the status is undefined.
[Program]
global: ListNode: listHead // stores the first node in the list
○ addNode(integer: pos, character: val)
ListNode: prev, newNode
integer: i
newNode ← ListNode()
newNode.val ← val
if (pos is equal to 1)
newNode.next ← listHead
listHead ← newNode
else
prev ← listHead
/* if pos is equal to 2, the following iteration process is not executed */
for (increase i from 2 to pos - 1 by 1)
prev ← prev.next
endfor
newNode.next ← prev.next
blank ← newNode
endif

Answer group

Explanation

prev.next — once the new node has taken over prev's successor, prev must point to the new node.

The loop stops with prev at node pos - 1, the node just before the insertion point. Insertion then changes two references: newNode.next ← prev.next keeps the rest of the list behind the new node, and prev.next ← newNode puts the new node after prev.

Example: for the list A → B → C, addNode(3, 'X') runs the loop once (i = 2), so prev is B; X's next becomes C and B's next becomes X, giving A → B → X → C.

Answer (e)

Why not others:

  • •(a) — makes the new node the head: the example list becomes X → C, losing A and B
  • •(b) — listHead.next is the right field only when pos is 2; in the example it gives A → X → C, losing B
  • •(c) — listHead.next.next is also a fixed position, right only when pos is 3; for pos 2 it sets B's next to X while X's next is B, forming a loop
  • •(d) — assigns to the local variable prev only; no node's next changes, so the new node is never linked in
  • •(f) — prev.next is still the old successor C, so C's next becomes X while X's next is C: a loop, with B still pointing at C

Key rule: To insert after a node, set the new node's next first and the predecessor's next second; assigning to a local reference variable never changes the list itself.

Linked List · AI-written, may contain errors

Practice this exam

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.