応用情報技術者 2019年 秋期 午前2 問06

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

要点まとめ

• 結論：末尾のデータを削除する処理（エ）が最も多くポインタをたどる必要があります。
• 根拠：単方向リストは前方向のみのリンクで、末尾の削除は先頭から末尾直前まで探索が必要です。
• 差がつくポイント：追加や先頭削除はポインタ操作が少なく済みますが、末尾削除は線形探索が必須で時間がかかります。

正解の理由

• 先頭にデータを追加（ア）は先頭ポインタの更新だけで済みます。
• 先頭のデータを削除（イ）も先頭ポインタを次のノードに変えるだけで済みます。
• 末尾にデータを追加（ウ）は末尾ポインタが直接参照できるため、ポインタをたどる必要はありません。
• 末尾のデータを削除（エ）は、末尾の一つ前のノードを探すために先頭から順に全ノードをたどる必要があり、最も多くポインタをたどります。
  したがって、正解はエです。

よくある誤解

解法ステップ

1. 単方向リストの構造を確認し、各ノードは次のノードへのポインタのみ持つことを理解する。
2. 先頭ポインタと末尾ポインタの役割を整理する。
3. 各操作（追加・削除）で必要なポインタのたどり方を考える。
4. 先頭追加・先頭削除はポインタの更新のみで済むことを確認。
5. 末尾追加は末尾ポインタで直接アクセス可能なためポインタたどりは不要。
6. 末尾削除は末尾の一つ前のノードを探すため、先頭から順に全ノードをたどる必要があることを理解。
7. 最も多くポインタをたどるのは末尾削除であると結論づける。

選択肢別の誤答解説

• ア: 先頭にデータを追加する処理
  → 先頭ポインタの更新だけで済み、ポインタをたどる回数は少ない。
• イ: 先頭のデータを削除する処理
  → 先頭ポインタを次のノードに変えるだけで済む。
• ウ: 末尾にデータを追加する処理
  → 末尾ポインタがあるため、直接末尾に追加できる。
• エ: 末尾のデータを削除する処理
  → 末尾の一つ前のノードを探すため、先頭から順に全ノードをたどる必要がある。

補足コラム

FAQ