IPA FE Subject B first sample Question 3

Topic: Linked List

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

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

The procedure append adds the character given as the argument to a singly linked list. Each element of the singly linked list is represented by the class ListElement. The figure shows the explanation of the class ListElement. ListElement-type variables store references to instances of the class ListElement. The global variable listHead stores a reference to the head element of the singly linked list. When the list is empty, listHead is undefined.

Member variableTypeDescription
valcharacterThe character to be stored in the list.
nextListElementReference to the instance that holds the next character in the list. Its initial state is undefined.
ConstructorDescription
ListElement(character: qVal)Initializes the member variable val with the argument qVal.

Figure Explanation of the class ListElement

[Program]
global: ListElement: listHead ← undefined
○ append(character: qVal)
ListElement: prev, curr
curr ← ListElement(qVal)
if (listHead is A)
listHead ← curr
else
prev ← listHead
while (prev.next is not undefined)
prev ← prev.next
endwhile
prev.next ← B
endif

Answer group

OptionAB

Explanation

A: undefined, B: curr — an empty list takes the new element as its head; otherwise the new element is linked after the last one.

curr is the new element: the constructor sets its val to qVal, and its next is undefined. When the list is empty, listHead is undefined and the new element becomes the head, so A is undefined. Otherwise prev starts at the head and the while loop moves it on until prev.next is undefined, so it stops on the last element. Setting prev.next ← curr links the new element after it, so B is curr; its own next is undefined, so it is the new tail.

Run from an empty list, appending “X”, “Y” and “Z” with (a) gives X → Y → Z.

Answer (a)

Why not others:

  • •(b) — curr.next is undefined, so the last element's next stays undefined and nothing after the first character is ever added
  • •(c) — listHead links the last element back to the head: the second call makes the head point to itself, and the third never leaves the while loop
  • •(d), (e) and (f) — with A as not undefined, an empty list goes to else, where prev is undefined and prev.next cannot be read; a non-empty list would have its head replaced by the new element, losing the rest

Key rule: To append to a singly linked list, set the head when the list is empty; otherwise walk to the element whose next is undefined and set that next to the new element.

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.