HOME»ネットワークスペシャリスト令和元年秋期»午前Ⅰ 問4
ネットワークスペシャリスト令和元年秋期 午前Ⅰ 問4
問4
先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。
- 先頭にデータを追加する処理
- 先頭のデータを削除する処理
- 末尾にデータを追加する処理
- 末尾のデータを削除する処理
- [出典]
- 応用情報技術者
令和元年秋期 問6と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
エ
解説
リスト構造は、隣接するデータ同士をポインタで連結して表現するデータ構造です。
- 追加するデータの次ノードポインタに、現在の先頭ポインタの値を設定
- 先頭ポインタに、追加するデータを指すポインタを設定
- 先頭ポインタをたどって先頭データを参照
- 先頭ポインタに、先頭データが持つ次ノードポインタの値を設定
- 末尾ポインタをたどって末尾データを参照
- 末尾データの次ノードポインタに、追加するデータを指すポインタを設定
- 末尾ポインタに、追加するデータを指すポインタを設定
- 正しい。末尾のデータを削除するには、末尾の一つ前のデータの次ノードポインタを空にして、末尾ポインタに末尾の一つ前のデータを指すポインタを設定しなくてはなりません。単方向リストでは、末尾のデータから前のデータに遡ることはできないので、先頭から末尾の一つ前まで順番にポインタをたどっていく必要があります。
つまり「末尾のデータを削除する処理」の場合、ポインタをたどる回数はリストが保持するデータ数にほぼ等しい回数となり、「エ」以外の処理と比較してポインタをたどる回数が極端に多くなることがわかります。