アルゴリズムとプログラミング
平成30年度 春期 基本情報技術者試験 午前 問6
リストを二つの 1 次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入り，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの 3 番目と 4 番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭（1 番目）の要素を指し，next[i] の値が 0 である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。
添字 0〜9 の表。box: 0=（空白）,1=A,2=B,3=C,4=D,5=E,6=F,7=G,8=H,9=I。next: 0=1,1=5,2=0,3=7,4=（空白）,5=3,6=（空白）,7=2,8=（空白）,9=（空白）。
- ア 3
- イ 5
- ウ 7
- エ 8
出典：平成30年度 春期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：ウ
覚える知識
配列で実現したリストへの要素挿入(next更新)
連結リストへの挿入では、新要素のnextに挿入位置の次要素の番号を入れ、前要素のnextを新要素の番号へ書き換える。
この問題で必要なこと
next[0]=1→1(A)→5(E)→3(C)→7(G)→2(B)→0 の順。3番目はC(3)、4番目はG(7)。Hの要素8を挿入するとnext[3]=8、next[8]=7(元の次の番号)となる。
ひっかけ
新要素のnextに前要素の番号を入れてしまう、リストの順序を添字順と取り違える。
この知識の出題：本試験系 1 回・免除試験 2 回（公開問題での観測値）