配列による単方向リスト表現とポインタ走査

正解は「エ」です。 本問は、2つの配列 `dataList`(要素値)と `pointerList`(次ポインタ)を用いて表現された単方向リストを、先頭ノードから順番に走査して新しい配列 `linearList` へ値を詰め替える処理です。 1. 空欄 `  a  `(終了条件): 単方向リストの各ノードにおいて、次の要素のインデックスは `pointerList  p  ` に保持されています。リストの末尾ノードでは次のノードが存在しないため、`pointerList  p  ` の値が「未定義」となっています(図1の例では末尾ノード `dataList  4  =40` に対応する `pointerList  4  ` が未定義)。 したがって、現在の要素 `dataList  p  ` を追加した直後に「次の要素が存在するかどうか」を判定するため、条件式は「`pointerList  p  が 未定義`」となります。 2. 空欄 `  b  `(ポインタの更新): 次の要素が存在する場合、走査対象のポインタ $$p$$ を次のノードの添字に進める必要があります。次ノードの添字は `pointerList  p  ` に格納されているため、代入式は `p ← pointerList  p  ` となります。 したがって、  a  = `pointerList  p  `、  b  = `pointerList  p  ` となる選択肢エが正解です。  a  に `dataList  p  ` を指定すると、要素値自体が未定義かどうかの判定になってしまい、末尾ノードの有効な値(40)を追加した時点で終了できなくなります。また  b  で `p ← i` とするとポインタ構造をたどれず誤りです。  a  に `dataList  p  ` を指定しているため不適切です。  b  で `p ← i` とすると、リストのポインタ順(1→3→2→4)ではなく単なる配列順(1, 2, 3...)になってしまい誤りです。

次のプログラム中の  a  と  b  に入れる正しい答えの組合せを,解答群の中から選べ。ここで,配列の要素番号は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 である。

問題画像

関数orderList は,図1 のdataList 及びpointerList で表現した単方向リストの値を,単方向リストの先頭からたどって順番に格納した配列を返す。関数orderList が返す配列を図2 に示す。

問題画像

〔プログラム〕

大域: 整数型の配列: 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
出典令和8年度 基本情報技術者試験 科目B 問4

a

b

ア

dataList p 

i

イ

dataList p 

pointerList p 

ウ

pointerList p 

i

エ

pointerList p 

pointerList p