システムアーキテクト 2019年 午前2 問07

挿入順の網羅性【午前2解説】

正解の理由

解法ステップ

1. 「挿入位置の分類」を確認する：初回（空）、先頭、途中（中間）、末尾の4種類を想定する。実務的には初回は別扱いだが、先頭・中間・末尾は必須検証ポイント。
2. 各選択肢を左から順にシミュレーションする（現在のリスト状態を逐次書く）。
3. 各入力ごとに「どの位置に挿入されるか」を判定する（先頭／途中／末尾）。
4. 1〜3を通して、先頭・途中・末尾の3種類が少なくとも一度ずつ出現するかを確認する。
5. 3種類すべて出現する選択肢を正解とする。

選択肢別の誤答解説

• 挙動（逐次状態と挿入位置）
  • 1 → [1] （初回）
  • 3 → [1, 3] （末尾挿入）
  • 2 → [1, 2, 3] （途中挿入）
  • 4 → [1, 2, 3, 4] （末尾挿入）
• 評価：途中挿入と末尾挿入は検証できるが、「既存要素がある状態での先頭挿入」が発生しないため、先頭処理の検証が不足。よって不十分。

• 挙動
  • 3 → [3] （初回）
  • 1 → [1, 3] （先頭挿入）
  • 4 → [1, 3, 4] （末尾挿入）
  • 2 → [1, 2, 3, 4] （途中挿入）
• 評価：先頭・途中・末尾のすべてを含み、網羅性が高い。したがって本問では適切。

• 挙動（重要）
  • 3 → [3] （初回）
  • 4 → [3, 4] （末尾挿入）
  • 2 → [2, 3, 4] （先頭挿入：2 は 3 の前に入る）
  • 1 → [1, 2, 3, 4] （先頭挿入：1 は 2 の前に入る）
• 評価：この順序では末尾挿入と先頭挿入は確認できるが、途中（中間）挿入は発生しないため網羅性が不足します。なお、「3,4,2,1」を順に挿入した場合、3→[3], 4→[3,4]（末尾挿入）, 2→[2,3,4]（先頭挿入）, 1→[1,2,3,4]（先頭挿入）となり、途中挿入は起きません。よって途中挿入の検証が抜けている点で不適切です。

• 挙動
  • 4 → [4] （初回）
  • 3 → [3, 4] （先頭挿入）
  • 2 → [2, 3, 4] （先頭挿入）
  • 1 → [1, 2, 3, 4] （先頭挿入）
• 評価：先頭挿入しか起きないため、途中・末尾の検証がまったくできず最も網羅性が低い。

よくある誤解

• 初回挿入＝先頭／末尾の検証と誤認する：空リストへの初回挿入は必須だが、既に要素がある状態での先頭挿入（先頭処理の分岐）が別途必要である点を見落としがちです。
• 「降順で挿入すれば途中挿入が起きる」と勘違い：降順に入力すると確かに先頭挿入が連続して発生しがちで、途中挿入は発生しないことが多い点に注意してください（例：4,3,2,1 は先頭のみ）。
• 1例で全網羅できると考える誤り：要素数や入力順によっては途中挿入が発生しないため、挿入回数や順序を慎重に設計する必要があります。

補足コラム

• 最小必要要素数：初期空リストから「先頭」「途中」「末尾」の3種類すべてを確認するには、一般に少なくとも4回の挿入を用いるケースが多いです（初回 + 先頭/途中/末尾 を別々に発生させるため）。3個の要素だと3通りの位置をすべて同一実行で得ることは基本的に困難です。
• 代替例：イ以外にも網羅性を満たす順序は存在します。例えば 2, 4, 1, 3 の順に挿入すると（2→[2], 4→末尾, 1→先頭, 3→途中）となり、先頭・途中・末尾をすべて含みます。テスト作成時は「現在のリスト状態」を逐次追って挿入位置を確認する習慣をつけると設計ミスを防げます。
• 追加検証：重複キーの扱い、安定性（同値要素の挿入位置）、双方向リストや配列実装でのシフトコストなども別途テストしておくと実戦的です。

FAQ