応用情報技術者試験 応用情報技術者試験 令和5年度秋期 午前 問5: 双方向リストを三つの一次元配列 elem[i]，next[i]，prev[i] の組で実現する。双方向リストが図の状態のとき，要素 D の次に要素 C を挿入し

問題本文

双方向リストを三つの一次元配列 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 である要素は，それぞれ双方向リストの末尾，先頭を表す。 ・双方向リストへの要素の追加は，一次元配列の末尾に追加

選択肢

• ア.next[6]=2，prev[6]=3
• イ.next[6]=3，prev[6]=4
• ウ.next[6]=5，prev[6]=3
• エ.next[6]=5，prev[6]=4

正解

ウ. next[6]=5，prev[6]=3

解説

双方向リストへの要素挿入で，新要素の next(次の要素番号)と prev(前の要素番号)に何が入るかを問う問題です。挿入する要素Cは配列末尾の要素番号6に追加され，Dの直後に入ります。図より要素Dは要素番号3にあり，挿入前は D の next が5(=要素E)を指しています。Cを「Dの次」に挿入すると，Cの前はD(要素番号3)，Cの次はもともとDの次だったE(要素番号5)になるので，next[6]=5，prev[6]=3となり正解はウです。(あわせて prev[5] は6に，next[3] は6に書き換えられます。)