単方向リストとポインタによるデータの探索【基本情報技術者試験 科目B 公開問題】

← 科目Bの公開問題一覧へ戻る

　基本情報技術者試験の科目Bの公開問題を題材に，単方向リストとポインタによるデータの探索について学習します。この問題では，ポインタを使って単方向リストを先頭から順番にたどる処理を確認します。

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

問　次のプログラム中の 　　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

解答群

	a	b
ア	dataList[p]	i
イ	dataList[p]	pointerList[p]
ウ	pointerList[p]	i
エ	pointerList[p]	pointerList[p]

【参考】	「データ構造の基礎まとめ（リストとは）」 「オブジェクト指向設計の基礎まとめ」 「オブジェクト指向プログラミング（C#）」

この問題のポイント

　この問題から学べることは，

• 単方向リストの基本的な構造
• dataListとpointerListを使ってリストを表現する方法
• ポインタを使って次の要素をたどる方法
• 未定義のポインタを利用してリストの末尾を判定する方法
• トレース表を使って，リストをたどる処理を追跡する方法

です。特に，pointerList[p] に格納された要素番号を利用して次の要素へ移動し，pointerList[p] が未定義になったところでリストの末尾と判断する処理を理解しておきましょう。

基本情報技術者試験の学習におすすめの参考書

基本情報技術者試験の合格を目指す方におすすめの参考書です。