応用情報技術者 2023年 秋期 午前2 問05
問題文
双方向リストを三つの一次元配列 elem[i]、next[i]、prev[i]の組で実現する。双方向リストが図の状態のとき、要素 Dの次に要素 C を挿入した後のnext[6]、prev[6]の値の組合せはどれか。ここで、双方向リストは次のように表現する。
・双方向リストの要素は、elem[i]に値、next[i] に次の要素の要素番号、prev [i]に前の要素の要素番号を設定
・双方向リストの先頭、末尾の要素番号は、それぞれ変数 Head, Tail に設定
・next[i]、prev[i]の値が0である要素は、それぞれ双方向リストの末尾、先頭を表す。
・双方向リストへの要素の追加は、一次元配列の末尾に追加
選択肢
ア：
イ：
ウ：（正解）
エ：
双方向リストの配列実装における要素挿入【午前2 解説】
要点まとめ
- 結論：要素Dの次にCを挿入すると、next[6]は5、prev[6]は3となる。
- 根拠：双方向リストの挿入は、挿入位置の前後の要素のnextとprevを適切に更新し、挿入要素のnextとprevを設定する必要がある。
- 差がつくポイント：配列での双方向リスト実装では、要素番号の管理とnext・prevの更新ミスが多いので、挿入前後の関係を正確に把握することが重要。
正解の理由
選択肢ウの next[6] = 5、prev[6] = 3 は、要素D（elem[3]）の次に新要素C（elem[6]）を挿入した場合の正しいリンク関係を示しています。
具体的には、Dの次は元々E（elem[5]）だったため、CのnextはEの要素番号5、CのprevはDの要素番号3となります。
また、Dのnextを6に、Eのprevを6に更新することで双方向リストの整合性が保たれます。
具体的には、Dの次は元々E（elem[5]）だったため、CのnextはEの要素番号5、CのprevはDの要素番号3となります。
また、Dのnextを6に、Eのprevを6に更新することで双方向リストの整合性が保たれます。
よくある誤解
- 挿入要素のnextやprevを誤って元の要素番号のままにする。
- 挿入位置の前後の要素のリンクを更新し忘れる。
- nextやprevの0の意味（先頭・末尾）を混同する。
解法ステップ
- 挿入位置の要素Dの要素番号を確認（3）。
- Dの次の要素番号を確認（5）。
- 新要素Cは配列の末尾（6）に追加。
- CのprevをDの要素番号3に設定。
- CのnextをDの次の要素番号5に設定。
- Dのnextを6に更新。
- E（5）のprevを6に更新。
選択肢別の誤答解説
- ア（next[6]=2, prev[6]=3）：nextが2はEの次の要素番号でなく誤り。
- イ（next[6]=3, prev[6]=4）：nextが3はDの要素番号で誤り。prevが4はBの要素番号で誤り。
- ウ（next[6]=5, prev[6]=3）：正解。Dの次にCを挿入した場合の正しいリンク。
- エ（next[6]=5, prev[6]=4）：prevが4はBの要素番号で誤り。Cの前はD（3）であるべき。
補足コラム
双方向リストを配列で実装する場合、ポインタの代わりに要素番号を使うため、next[i]やprev[i]の値が0の意味（先頭・末尾）を正確に理解することが重要です。
また、挿入や削除の際はリンクの前後関係を丁寧に更新しないとリストの整合性が崩れます。
また、挿入や削除の際はリンクの前後関係を丁寧に更新しないとリストの整合性が崩れます。
FAQ
Q: なぜnext[i]やprev[i]が0のときは先頭や末尾を表すのですか？
A: 0は配列の有効な要素番号に含まれないため、リストの端を示す特別な値として使われます。
A: 0は配列の有効な要素番号に含まれないため、リストの端を示す特別な値として使われます。
Q: 配列の末尾に追加するとはどういう意味ですか？
A: 新しい要素はelem配列の空いている最後のインデックスに格納し、そのインデックスを要素番号として扱います。
A: 新しい要素はelem配列の空いている最後のインデックスに格納し、そのインデックスを要素番号として扱います。
関連キーワード: 双方向リスト、配列実装、next配列、prev配列、データ構造、リスト挿入、ポインタ代替
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！