令和5年度 秋期 応用情報技術者試験 午前 問5
双方向リストを三つの一次元配列 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 である要素は，それぞれ双方向リストの末尾，先頭を表す。- 双方向リストへの要素の追加は，一次元配列の末尾に追加
図の説明テキスト
配列と変数の状態を示す図。図の上部には「一次元配列の末尾」という記述があり、要素番号6の列を点線の枠で囲んでいる。
- elem配列:
要素番号: 1, 2, 3, 4, 5, 6
値: A, F, D, B, E, (空欄) - next配列:
要素番号: 1, 2, 3, 4, 5, 6
値: 4, 0, 5, 3, 2, (空欄) - prev配列:
要素番号: 1, 2, 3, 4, 5, 6
値: 0, 5, 4, 1, 3, (空欄) - Head変数: 1
- Tail変数: 2
解答・解説
正解: ウ. next[6]: 5, prev[6]: 3
正解の根拠
双方向リストを配列の組 elem[i], next[i], prev[i] で表現する仕組みに関する問題です。
問題文の条件より、双方向リストへの要素の追加は一次元配列の末尾に行われるため、新しく追加される「要素C」の要素番号は 6 となります。
「要素Dの次に要素Cを挿入する」という操作は、既存の要素Dと、その次の要素の間に要素Cを連結することを意味します。
正解の選択肢から逆算すると、挿入前の状態で要素Dの要素番号は 3、要素Dの次の要素番号は 5 であったことが分かります。
要素C（要素番号 6）を要素D（要素番号 3）の次に挿入する際のポインタ（インデックス）の付け替え処理は以下のようになります。
- 新しい要素Cの前の要素は要素Dになるため、
prev[6]に 3 を設定する。 - 新しい要素Cの次の要素は元々要素Dの次だった要素になるため、
next[6]に 5 を設定する。 - 要素Dの次の要素を要素Cにするため、
next[3]を 6 に更新する。 - 元々要素Dの次だった要素（番号5）の前の要素を要素Cにするため、
prev[5]を 6 に更新する。
上記 1. と 2. の結果から、挿入後の値は next[6]: 5, prev[6]: 3 となります。
各選択肢の解説
- ア (
next[6]: 2,prev[6]: 3): 要素Dの次の要素番号が 2 であった場合の組み合わせですが、本来の双方向リストの状態（要素Dの次が 5）と異なるため誤りです。 - イ (
next[6]: 3,prev[6]: 4):nextとprevの設定値が誤っています。これでは要素Cの前が要素番号4、次が要素番号3の間に挿入されてしまいます。 - ウ (
next[6]: 5,prev[6]: 3): 正解です。要素Cが、要素D（番号3）とその次の要素（番号5）の間に正しく挿入されています。 - エ (
next[6]: 5,prev[6]: 4):prev[6]の値が誤っています。これでは要素Cの前が要素番号4になってしまい、「要素Dの次に挿入する」という条件を満たしません。