ITPEC FE Subject B April 2024 Question 10

Topic: Linked List

From the answer group below, select the correct combination of answers to be inserted into A and B in the program.

The procedure Insert inserts an integer number given by the argument after the last element of the linear circular linked list. Each element of the linear circular linked list is represented by the class ListElement. The figure shows the description of the class ListElement. The ListElement-type variable holds a reference to an instance of the class ListElement. The global variable listHead holds a reference to the head element of the linear circular linked list. Remember that in the circular linked list the last element points to the listHead. Here, if the list is empty, listHead is set to undefined.

Member variableTypeDescription
valintegerThe value of an element.
nextListElementReference to the instance that holds the next element in the list.
ConstructorDescription
ListElement(integer: newItem)Initialize the member variable val with the argument newItem.

Figure Class ListElement

[Program]
global: ListElement: listHead ← undefined
○ Insert(integer: newItem)
ListElement: tmp, newNode
newNode ← ListElement(newItem)
if (listHead is undefined)
listHead ← newNode
listHead.next ← listHead
else
tmp ← listHead
while (tmp.next is not A)
tmp ← B
endwhile
tmp.next ← newNode
newNode.next ← listHead
endif

Answer group

OptionAB

Explanation

A: listHead, B: tmp.next — walk from the head to the node whose next leads back to the head; that node is the last element.

  • •In a circular list the last element's next is listHead, so the loop moves on while tmp.next is not listHead: A is listHead.
  • •Moving on means following the link: B is tmp.next.
  • •After the loop tmp is the last element. tmp.next ← newNode hangs the new node after it, and newNode.next ← listHead closes the circle again.

Trace: the list is 5 → 7 → back to 5, and 9 is inserted. tmp starts at 5, whose next is 7, not the head, so tmp moves to 7. The next of 7 is the head, so the loop stops. Then 7 links to 9 and 9 links to 5, giving 5 → 7 → 9 → back to 5.

Answer (b)

Why not others:

  • •(a) — newNode is not in the list yet, so tmp.next never equals it, and tmp ← listHead.next sets the same node on every pass: the loop never ends
  • •(c) — tmp ← listHead puts tmp back at the head on every pass, and the head's next is never the head itself once there are two elements, so the loop never ends
  • •(d) — newNode.next has not been set yet, so with two or more elements tmp becomes undefined and the next tmp.next test fails

Key rule: To reach the tail of a circular list, stop at the node whose next is the head and advance with tmp ← tmp.next; a loop whose variable never moves along the list cannot terminate.

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.