令和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である要素は，それぞれ双方向リストの末尾，先頭を表す。・双方向リストへの要素の追加は，一次元配列の末尾に追加
- ア next[6]=2, prev[6]=3
- イ next[6]=3, prev[6]=4
- ウ next[6]=5, prev[6]=3
- エ next[6]=5, prev[6]=4
解答・解説を見る
正解：ウ
AI解説
双方向リストでは要素を配列の末尾に追加するため、Dの次にCを挿入すると新要素は配列の末尾(添字6)に置かれる。挿入後、新要素(添字6)のnextにはDの元の次要素の添字、prevにはDの添字が設定される必要があり、図の状態から求めるとnext[6]=5、prev[6]=3となる。 ア: next[6]の値がずれており、Dの次に来るべき要素の添字と一致しないため誤りである。 イ: prev[6]の値がDの添字と一致しておらず、挿入位置の前後関係が正しく表されていないため誤りである。 ウ: 新要素(添字6)の次(next)には元々Dの次であった要素の添字5が、前(prev)にはDの添字3が入り、これがDとその次要素の間にCを挿入した正しい状態であり正解である。 エ: prev[6]の値がずれており、Dの添字と一致しないため誤りである。 💡 双方向リストへの挿入問題は、配列の末尾に新要素を追加した上で、挿入位置前後のnext・prevのポインタの張り替え(4か所)を図に沿って一つずつ確認するのが確実である。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。