連結リストの途中挿入で参照先をどう更新するか
基本情報技術者試験 平成30年度春期 午前 問6 ／ アルゴリズムとプログラミング › データ構造
過去問にチャレンジ
リストを二つの1次元配列で実現する。配列要素 box[i] と next[i] の対がリストの一つの要素に対応し，box[i] に要素の値が入り，next[i] に次の要素の番号が入る。配列が図の状態の場合，リストの3番目と4番目との間に値が H である要素を挿入したときの next[8] の値はどれか。ここで，next[0] がリストの先頭(1番目)の要素を指し，next[i] の値が0である要素はリストの最後を示し，next[i] の値が空白である要素はリストに連結されていない。
- ア
3
- イ
5
- ウ
7
- エ
8
会話形式の解説
講師まず、リストの順番をnextが指す先から確かめましょう。添字の順に並んでいるとは限りません。
受験者boxではHが添字8にありますが、その前後は表を見るだけでは決められませんね。
講師はい。next[0]は1を指します。そこからたどると、添字は1→5→3→7→2で、値はA→E→C→G→Bです。
受験者3番目がC、4番目がGです。Hを入れると、C→H→Gになりますね。
講師そのとおりです。Cの添字は3、Hの添字は8なので、CからHへ進むようnext[3]を8にします。では、next[8]はどこを指しますか。
受験者Hの次はGです。Gの添字は7なので、next[8]には7を入れます。
講師正解です。3を入れるとHから直前のCへ戻ってしまいます。5は2番目のEの添字なので、Hの次には当たりません。
受験者8はH自身の添字ですから、next[8]を8にするとHから先へ進めませんね。
講師はい。nextに入れるのは次の要素の値ではなく、その要素の添字です。挿入では直前の要素と、挿入する要素の参照先をそれぞれ確かめましょう。
まとめ
リストの並びはboxの添字順ではなく、next[0]からたどって確認します。挿入前の並びはA→E→C→G→Bで、Hを入れる位置はCとGの間です。Hの次は添字7のGなので、next[8]は7、正解はウです。
解答・解説
正解はウです
この問題のテーマ
配列で表した連結リストで、要素を途中に挿入するときの参照先を問う問題です。
解き方の考え方
next[0]から順にたどると、添字は1→5→3→7→2となり、要素はA→E→C→G→Bの順です。3番目のCと4番目のGの間に、添字8のHを入れます。CからHへつなぐためにnext[3]を8にし、HからGへつなぐためにnext[8]を7にします。
選択肢ごとの解説
- ×ア 33はHの直前にあるCの添字です。HからCへ戻す値ではないため、next[8]には入りません。
- ×イ 55は2番目のEの添字です。Hの次に来るのはGなので、next[8]は5ではありません。
- ○ウ 77はGの添字です。挿入後、Hの次はGになるので、next[8]の値は7です。
- ×エ 88はH自身の添字です。next[8]を8にするとHが自分自身を指し、次のGへ進めません。
POINT
- リストの並びは、boxの添字順ではなく、nextが指す先をたどって確認します。
- 途中への挿入では、直前の要素と挿入する要素の参照先を更新します。
- nextに入れるのは要素の値ではなく、次の要素の添字です。