基本情報技術者 2018年 春期 午前（科目A） 問06
問題文
リストを二つの1次元配列で実現する。配列要素box[i]とnext[i]の対がリストの一つの要素に対応し、box[i]に要素の値が入り、next[i]に次の要素の番号が入る。配列が図の状態の場合、リストの3番目と4番目との間に値がHである要素を挿入したときのnext[8]の値はどれか。ここで、next[0]がリストの先頭（1番目）の要素を指し、next[i]の値が0である要素はリストの最後を示し、next[i]の値が空白である要素はリストに連結されていない。
選択肢
ア：3
イ：5
ウ：7（正解）
エ：8
🔒 解説は解答すると表示されます
配列による単方向リスト挿入【午前解説】
正解の理由
配列表現の連結リストでは next[0] が先頭を示し，next[i]=0 が末尾を示します。図より先頭は next[0]=1 で，辿ると 1 → 5 → 3 → 7 → 2 → 0 の順になります。
3 番目の要素はインデックス 3（値 C），4 番目はインデックス 7（値 G）です。値 H は index 8 に格納するので，挿入のために次の操作を行います：next[8] に元々 3 の次であった 7 を代入し，その後 next[3] を 8 に変更します。したがって next[8] の値は 7 であり，選択肢では ウ が正解です。
3 番目の要素はインデックス 3（値 C），4 番目はインデックス 7（値 G）です。値 H は index 8 に格納するので，挿入のために次の操作を行います：next[8] に元々 3 の次であった 7 を代入し，その後 next[3] を 8 に変更します。したがって next[8] の値は 7 であり，選択肢では ウ が正解です。
解法ステップ
- next[0] から始めて next を辿り，現在の連結順を求める（1 → 5 → 3 → 7 → 2 → 0）。
- 3 番目と 4 番目の要素を確認する（3 番目はインデックス 3、4 番目はインデックス 7）。
- 挿入するノードのインデックス（ここでは 8）を決める（box[8]=H）。
- next[8] に元の prev（3）の次を代入する（next[8] = next[3] = 7）。
- prev の next を new に更新する（next[3] = 8）。これで 3 → 8 → 7 の連結が完成する。
選択肢別の誤答解説
- ア: 3
誤り。これは next[8] を prev（挿入位置の直前ノード）にしてしまう誤解。正しくは prev の次を指す値を new に代入するので 3 ではなく 7 です。 - イ: 5
誤り。5 はリスト中の別ノード（2 番目）への参照で，3 と 7 の間の挿入とは無関係です。next[5] は既に 3 を指しています。 - ウ: 7
正解。挿入後 new（8）の次は元々 prev（3）が指していたノード 7 になるため next[8]=7 となります。 - エ: 8
誤り。self reference（自分自身を指す）はループを作り意図しない構造になります。挿入時は new が元の次を指すべきで自己参照ではありません。
よくある誤解
- 「next[i]=0 を未使用の意味と誤解」：ここでは next[i]=0 がリストの末尾（NULL）を意味し，未使用セルは空白で示されています。
- 「挿入時の代入順を逆にする」：先に prev の next を new にしてしまうと元の次要素を失い next[new] に正しい値を入れられません。
- 「要素番号と要素の順序を混同する」：k 番目の要素の中身（箱の値）と配列インデックス（ノード番号）を取り違えるミスが多いです。
補足コラム
配列で連結リストを実装する方式は，ポインタの代わりに配列インデックスを使う古典的手法です。挿入操作の安全な手順は常に次の通りです：
- next[new] = next[prev]
- next[prev] = new
この順序を守ることでリンクを失う事故を防げます。空きセル管理（フリーリスト）を用いれば，削除したセルを再利用できます。
参考として Python 風の擬似コード（インデックス基準は図と同様）：
# next: リストの next 配列（0-9）
# new = 8, prev = 3
next[new] = next[prev] # next[8] = 7
next[prev] = new # next[3] = 8
FAQ
Q1: next[0] が先頭ポインタなのはなぜですか？
A1: 図や設問でそう定義されているためです。配列実装では特殊セル（ここでは index 0）を先頭ポインタに使う慣習がよくあります。
A1: 図や設問でそう定義されているためです。配列実装では特殊セル（ここでは index 0）を先頭ポインタに使う慣習がよくあります。
Q2: next[i]=0 と空白はどう違いますか？
A2: next[i]=0 は「リストの末尾（NULL）」を示し，空白は「その配列要素がリストに連結されていない（未使用）」ことを示します。
A2: next[i]=0 は「リストの末尾（NULL）」を示し，空白は「その配列要素がリストに連結されていない（未使用）」ことを示します。
Q3: 空のリストに挿入するときはどうする？
A3: 先頭が空の場合（next[0] = 0 等），新ノードの next を 0 にして next[0] を新ノードのインデックスに設定します。
A3: 先頭が空の場合（next[0] = 0 等），新ノードの next を 0 にして next[0] を新ノードのインデックスに設定します。
関連キーワード: リスト、配列実装、連結リスト、挿入操作、ポインタ管理
\ せっかくなら /
基本情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！