応用情報技術者試験 令和5年秋 午前問5 解説付き過去問

この問題は、双方向リストに新しい要素を挿入したとき、参照情報（next配列とprev配列）がどのように変化するかを問うものです。以下に丁寧に解説します。

1. 双方向リストの構造
   双方向リストとは、各要素が前後の要素を参照（ポインタやインデックス）で持つリスト構造です。要素を先頭からも末尾からもたどれる特徴があります。

   この問題では、以下の3つの一次元配列で双方向リストを実現しています。

   • elem[i]：i番目の要素の値
   • next[i]：i番目の次の要素のインデックス
   • prev[i]：i番目の前の要素のインデックス

   また、next[i] = 0 ならその要素はリストの末尾、prev[i] = 0 ならその要素はリストの先頭であることを意味します。

   
   
   
2. 初期状態のリスト
   図を見ると、リストの構造は次のようになっています。

   Head → A（1）→ B（4）→ D（3）→ E（5）→ F（2）→ Tail

   括弧内は配列の添字です。

   
   
   
3. 要素Cの追加位置とインデックス
   要素CはDの次、Eの前に挿入されます。
   また、一次元配列の末尾に追加されるため、要素Cは elem[6] に格納されます。
   
   
   
4. 配列値の更新
   要素CをDとEの間に挿入するためには、以下のように値を設定します。
   1. prev[6] = 3（要素Dのインデックス）
      
      
   2. next[6] = 5（要素Eのインデックス）
      
      
   3. next[3] = 6（DからCへ）
      
      
   4. prev[5] = 6（EからCへ）
      
      

   この更新によって、D ↔ C ↔ E のリンクが正しく接続されます。

   
   
   
5. 答えの確認
   問題で問われているのは、要素C（添字6）の next[6] と prev[6] の組合せです。

   したがって、

   next[6] = 5
   prev[6] = 3

   
   
   

以上より、要素Dの次に要素Cを挿入したあとの next[6] = 5、prev[6] = 3 が正解となります。