データ構造 (全29問中13問目)

No.13

先頭ポインタと末尾ポインタをもち,多くのデータがポインタでつながった単方向の線形リストの処理のうち,処理ポインタ,末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで,単方向のリストは先頭ポインタからつながっているものとし,追加するデータはポインタをたどらなくても参照できるものとする。
  • 先頭にデータを追加する処理
  • 先頭のデータを削除する処理
  • 末尾にデータを追加する処理
  • 末尾のデータを削除する処理

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

  • 追加するデータの次ノードへの参照に現在の先頭ポインタをセットし、先頭ポインタに追加するデータへのポインタをセットします。ポインタをたどる回数は0回。
  • 現在の先頭のデータが持つ次ノードへの参照を、先頭ポインタにセットします。先頭ポインタ→先頭データで1回。
  • 末尾ポインタから末尾データへ飛び、末尾データの次ノードへの参照を追加するデータにする。末尾ポインタに追加するデータの参照をセットします。末尾ポインタ→末尾データで1回。
  • 末尾のデータを削除するには、末尾の一つ前の次ノードへの参照を空にして、末尾ポインタに末尾の一つ前のデータの参照をセットしなくてはなりません。単方向リストのため末尾のデータから一つ前のデータは参照できず、先頭から末尾の一つ前まで順番にポインタをたどっていく必要があります。
つまり「末尾のデータを削除する処理」の場合、ポインタをたどる回数はリストが保持するデータ数にほぼ等しい回数となり、「エ」以外の処理に比べて極端に多くなることが分かると思います。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop