令和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
| a | b | |
|---|---|---|
| ア | 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 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目大域: 整数型の配列: dataList ← {10, 30, 20, 40, 未定義の値} | dataList = {10, 30, 20, 40, 未定義} |
| 2 | 2行目大域: 整数型の配列: pointerList ← {3, 4, 2, 未定義の値, 未定義の値} | pointerList = {3, 4, 2, 未定義, 未定義} |
| 3 | 4行目○整数型の配列: orderList() | |
| 4 | 5行目整数型: i, p ← 1 | p = 1 |
| 5 | 6行目整数型の配列: linearList ← {} // 要素数0の配列 | linearList = {} |
| 6 | 7行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす) | 真 i = 1 |
| 7 | 8行目linearListの末尾 に dataList[p]の値 を追加する | linearList = {10} |
| 8 | 9行目if (pointerList[p] が 未定義) | 偽 |
| 9 | 12行目p ← pointerList[p] | p = 3 |
| 10 | 7行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす) | 真 i = 2 |
| 11 | 8行目linearListの末尾 に dataList[p]の値 を追加する | linearList = {10, 20} |
| 12 | 9行目if (pointerList[p] が 未定義) | 偽 |
| 13 | 12行目p ← pointerList[p] | p = 2 |
| 14 | 7行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす) | 真 i = 3 |
| 15 | 8行目linearListの末尾 に dataList[p]の値 を追加する | linearList = {10, 20, 30} |
| 16 | 9行目if (pointerList[p] が 未定義) | 偽 |
| 17 | 12行目p ← pointerList[p] | p = 4 |
| 18 | 7行目for (i を 1 から dataListの要素数 まで 1 ずつ増やす) | 真 i = 4 |
| 19 | 8行目linearListの末尾 に dataList[p]の値 を追加する | linearList = {10, 20, 30, 40} |
| 20 | 9行目if (pointerList[p] が 未定義) | 真 |
| 21 | 10行目繰返し処理を終了する | |
| 22 | 14行目return linearList |
戻り値:{10, 20, 30, 40}