うごく基本情報

令和8年度 公開問題 科目B 問4

連結リスト ・ 配列 ・ 未定義

次のプログラム中の[ ]と[ ]に入れる正しい答えの組合せを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
単方向リストを,配列 dataList と配列 pointerList の二つの配列で表現する。
dataList にリストの要素の値を格納し,pointerList にリストの次の要素に対応するdataList の要素番号を格納する。単方向リストの先頭は, dataList[1] 及びpointerList[1] の組みである。単方向リストの末尾に対応する pointerList の要素は未定義である。dataList のうち単方向リストの要素の値を格納していない要素と,対応する pointerList の要素は未定義である。
プログラムが扱う dataList 及び pointerList の内容を図 1 に示す。先頭の次の要素の要素番号は,pointerList[1] に格納された 3 であり,値は dataList[3] に格納された 20 である。その次の要素の要素番号は pointerList[3] に格納された 2 であり,値は dataList[2] に格納された 30 である。
要素番号 1 2 3 4 5dataList 10 30 20 40要素番号 1 2 3 4 5pointerList 3 4 2
注記網掛けはその要素が未定義であることを示す。
図 1 dataList 及び pointerList の内容関数 orderList は,図 1 の dataList 及び pointerList で表現した単方向リストの値を,単方向リストの先頭からたどって順番に格納した配列を返す。関数 orderListが返す配列を図 2 に示す。
要素番号 1 2 3 410 20 30 40
図 2 関数 orderList が返す配列

大域: 整数型の配列: dataList ← {10, 30, 20, 40, 未定義の値}
大域: 整数型の配列: pointerList ← {3, 4, 2, 未定義の値, 未定義の値}

○整数型の配列: orderList()
  整数型: i, p ← 1
  整数型の配列: linearList ← {}  // 要素数0の配列
  for (i を 1 から dataListの要素数 まで 1 ずつ増やす)
    linearListの末尾 に dataList[p]の値 を追加する
    if ([ a ] が 未定義)
      繰返し処理を終了する
    endif
    p ← [ b ]
  endfor
  return linearList
ab
アdataList[p]i
イdataList[p]pointerList[p]
ウpointerList[p]i
エpointerList[p]pointerList[p]

出典:令和8年度 基本情報技術者試験 科目B 公開問題 問4

正解と解説を見る

正解:エ

ポイント:配列で作る単方向リスト:次の位置は pointerList[p]。末尾は「次」が未定義なので、そこで止める。

dataList={10, 30, 20, 40, 未定義}、pointerList={3, 4, 2, 未定義, 未定義} です。先頭の dataList[1]=10 から、pointerList が指す番号をたどると、1 → 3 → 2 → 4 の順になり、値は 10, 20, 30, 40 です。
プログラムは、p の位置の値を linearList に追加し、次に進む位置を p に入れます。
・空欄b(次の位置):次の要素の番号は pointerList[p] なので p ← pointerList[p]。
・空欄a(終わりの判定):末尾の要素は「次」がない=pointerList[p] が未定義です。値を追加した直後に pointerList[p] が未定義なら、繰返しを終了します。
よって a、b とも pointerList[p] の(エ)。
イ:a を dataList[p] にすると、末尾(40)を追加した後も止まらず、p ← pointerList[4](未定義)となり、次の dataList[p] で実行時エラーになります。
ア・ウ:b を i にすると、リストをたどらずに配列の並び順で進んでしまいます。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

orderList() を呼び出したときに、1行ずつ何が起きるかの表です(全部で 22 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目大域: 整数型の配列: dataList ← {10, 30, 20, 40, 未定義の値}dataList = {10, 30, 20, 40, 未定義}
22行目大域: 整数型の配列: pointerList ← {3, 4, 2, 未定義の値, 未定義の値}pointerList = {3, 4, 2, 未定義, 未定義}
34行目○整数型の配列: orderList()
45行目整数型: i, p ← 1p = 1
56行目整数型の配列: linearList ← {} // 要素数0の配列linearList = {}
67行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす)真
i = 1
78行目linearListの末尾 に dataList[p]の値 を追加するlinearList = {10}
89行目if (pointerList[p] が 未定義)偽
912行目p ← pointerList[p]p = 3
107行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす)真
i = 2
118行目linearListの末尾 に dataList[p]の値 を追加するlinearList = {10, 20}
129行目if (pointerList[p] が 未定義)偽
1312行目p ← pointerList[p]p = 2
147行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす)真
i = 3
158行目linearListの末尾 に dataList[p]の値 を追加するlinearList = {10, 20, 30}
169行目if (pointerList[p] が 未定義)偽
1712行目p ← pointerList[p]p = 4
187行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす)真
i = 4
198行目linearListの末尾 に dataList[p]の値 を追加するlinearList = {10, 20, 30, 40}
209行目if (pointerList[p] が 未定義)真
2110行目繰返し処理を終了する
2214行目return linearList

戻り値:{10, 20, 30, 40}

サイトで、1行ずつ予想しながら動かす →