IPA FE Subject B sample Question 10

Topic: Linked List

A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問10, translated into English. ITPEC is based on the same exams.

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

The procedure delNode deletes the element at the position specified by the argument pos from a singly linked list. The argument pos is a positive integer that is equal to or less than the number of elements in the list. The position at the head of the list is 1.
The class ListElement represents an element of a singly linked list. The table shows an explanation of the member variables of the class ListElement. ListElement-type variables store references to instances of the class ListElement. A reference to the head element of the list is pre-stored in the global variable listHead.

Table Explanation of the member variables of the class ListElement

Member variableTypeDescription
valcharacterThe value of the element
nextListElementReference to the next elementIf there is no next element, the status is undefined
[Program]
global: ListElement: listHead // stores the head element of the list
○ delNode(integer: pos) /* pos is a positive integer equal to or less than the number of elements in the list */
ListElement: prev
integer: i
if (pos is equal to 1)
listHead ← listHead.next
else
prev ← listHead
/* if pos is equal to 2, the iteration process is not executed */
for (increase i from 2 to pos - 1 by 1)
prev ← prev.next
endfor
prev.next ← blank
endif

Answer group

Explanation

prev.next.next — to unlink the element at pos, the element before it must point to the element after it.

The loop runs i from 2 to pos − 1, so prev stops on element pos − 1, the one just before the element to delete. That element is prev.next, and the one after it is prev.next.next. Assigning it to prev.next skips the deleted element, and nothing else needs to change. When pos is the last position, prev.next.next is undefined, and prev becomes the new tail.

Example: for A → B → C → D, delNode(3) runs the loop once, so prev is B; B's next becomes D, giving A → B → D.

Answer (f)

Why not others:

  • •(e) — assigns prev.next its own value, so nothing is deleted
  • •(a) and (d) — point an element back at the head or at itself: for pos 2 the head's next becomes the head, a loop
  • •(b) and (c) — fixed positions counted from the head: (c) is right only when pos is 2 (then prev is listHead), (b) deletes nothing at pos 2 and forms a loop from pos 3

Key rule: To delete from a singly linked list, stop on the predecessor and set its next to its next.next; the head has no predecessor, so it is handled separately.

Linked List · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.