応用情報技術者 2010年 秋期 午前2 問05

先頭ポインタと末尾ポインタをもち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ、末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか【午前2 解説】

要点まとめ

• 結論：単方向リストで末尾のデータを削除する処理が最も多くポインタをたどる必要があります。
• 根拠：先頭ポインタと末尾ポインタは保持していても、末尾の前の要素を特定するには先頭から順に辿る必要があるためです。
• 差がつくポイント：単方向リストの構造理解と、各操作のポインタ追跡回数の違いを正確に把握することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 単方向リストの構造を理解する（各ノードは次のノードへのポインタのみ持つ）。
2. 先頭ポインタと末尾ポインタの役割を確認する。
3. 各操作（追加・削除）がどのノードに影響するかを考える。
4. 末尾のデータを削除する場合、末尾の前のノードを探す必要があることを認識する。
5. そのため、先頭から末尾の前まで全ノードを辿る必要があり、ポインタ追跡回数が最大になると判断する。

選択肢別の誤答解説

• ア: 先頭にデータを追加する処理
  → 先頭ポインタがあるため、追加は即座に行えポインタ追跡は少ない。
• イ: 先頭のデータを削除する処理
  → 先頭ポインタを更新するだけで済み、ポインタ追跡は最小限。
• ウ: 末尾にデータを追加する処理
  → 末尾ポインタがあるため、追加は即座に行える。
• エ: 末尾のデータを削除する処理
  → 末尾の前のノードを探すために先頭から辿る必要があり、最も多くポインタをたどる。

補足コラム

FAQ