平成22年秋期試験問題 午前問5
問5解説へ
先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。
- 先頭にデータを追加する処理
- 先頭のデータを削除する処理
- 末尾にデータを追加する処理
- 末尾のデータを削除する処理
広告
解説
リスト構造は、隣接するデータ同士をポインタで連結して表現するデータ構造です。
- 追加するデータの次ノードポインタに、現在の先頭ポインタの値を設定
- 先頭ポインタに、追加するデータを指すポインタを設定
- 先頭ポインタをたどって先頭データを参照
- 先頭ポインタに、先頭データが持つ次ノードポインタの値を設定
- 末尾ポインタをたどって末尾データを参照
- 末尾データの次ノードポインタに、追加するデータを指すポインタを設定
- 末尾ポインタに、追加するデータを指すポインタを設定
- 正しい。末尾のデータを削除するには、末尾の一つ前のデータの次ノードポインタを空にして、末尾ポインタに末尾の一つ前のデータを指すポインタを設定しなくてはなりません。単方向リストでは、末尾のデータから前のデータに遡ることはできないので、先頭から末尾の一つ前まで順番にポインタをたどっていく必要があります。
つまり「末尾のデータを削除する処理」の場合、ポインタをたどる回数はリストが保持するデータ数にほぼ等しい回数となり、「エ」以外の処理と比較してポインタをたどる回数が極端に多くなることがわかります。
広告