基本情報技術者試験 2006年度 = 平成18年度・秋期 午前 問13

 表は、配列を用いた連結セルによるリストの内部表現であり、リスト[東京,品川,名古屋,新大阪]を表している。このリストを[東京,新横浜,名古屋,新大阪]に変化させる操作はどれか。ここで、A(i , j )は表の第i 行第j 列の要素を表す。例えば、A(3, 1)=“名古屋”であり、A(3, 2)=4である。また、→は代入を表す。

           列        A     1    2        ┌──────┬──┐    1 │ “東京” │ 2 │      ├──────┼──┤ 行  2 │ “品川” │ 3 │      ├──────┼──┤    3 │ “名古屋” │ 4 │      ├──────┼──┤    4 │ “新大阪” │ 0 │      ├──────┼──┤    5 │ “新横浜” │  │      └──────┴──┘

第1の操作 第2の操作
5 → A(1,2) A(A(1,2) ,2) → A(5,2)
5 → A(1,2) A(A(2,2) ,2) → A(5,2)
A(A(1,2) ,2) → A(5,2) 5 → A(1,2)
A(A(2,2) ,2) → A(5,2) 5 → A(1,2)

解答



解説

 単方向リストは、各ノードが、後続ノードへのポインタをもつデータ構造であり、先頭ノードからポインタをたぐることによって、登録されているすべてのデータを取り出すことができるようになっています。
 本問で与えられたデータを、視覚的に分かりやすく表現すると、以下のようになります。なお、図中の→は、後続ノードへのポインタです。

 1           2           3           4 ┌──────┬──┐ ┌──────┬──┐ ┌──────┬──┐ ┌──────┬──┐ │ “東京” │ 2 │→│ “品川” │ 3 │→│ “名古屋” │ 4 │→│ “新大阪” │ 0 │ └──────┴──┘ └──────┴──┘ └──────┴──┘ └──────┴──┘  5 ┌──────┬──┐ │ “新横浜” │  │  ※リスト内には含まれず独立しています。 └──────┴──┘

 以下、ポインタの値を後続ポインタと呼ぶことにします。たとえば、“東京”の後続ポインタは2です。なお、“新大阪”の後続ポインタ0は、後続ノードが存在しないことを意味しています。
 本問は、リスト中の2番目に存在する“品川”を“新横浜”に入れかえる操作を問う問題です。正解は選択肢であり、以下のように操作します。

■Step 1 “東京”の後続ノードの後続ポインタを“新横浜”の後続ポインタにコピーする
 “東京”の後続ノードが格納されている位置はA(1, 2)によって得られます(値は2です)。そのノードの後続ポインタA(A(1,2) ,2)すなわちA(2, 2)を、“新横浜”の後続ポインタA(5,2)にコピーします。A(5, 2)に3が代入されますので、“新横浜”は“名古屋”を指すことになります。

 1           2           3           4 ┌──────┬──┐ ┌──────┬──┐ ┌──────┬──┐ ┌──────┬──┐ │ “東京” │ 2 │→│ “品川” │ 3 │→│ “名古屋” │ 4 │→│ “新大阪” │ 0 │ └──────┴──┘ └──────┴──┘ └──────┴──┘ └──────┴──┘                             5                         ┌──────┬──┐                │ “新横浜” │ ───────────────┘ └──────┴──┘

■Step 2 “東京”の指す先を“新横浜”とする
 “東京”の後続ノードを“新横浜”とするために、“東京”の後続ポインタA(1, 2)に5を代入します。その結果、どこからも指されない“品川”がリストから切り離されることになります。

 1           2           3           4 ┌──────┬──┐ ┌──────┬──┐ ┌──────┬──┐ ┌──────┬──┐ │ “東京” │ │ │ “品川” │ 3 │→│ “名古屋” │ 4 │→│ “新大阪” │ 0 │ └──────┴──┘ └──────┴──┘ └──────┴──┘ └──────┴──┘                          ↑  5                       │ ┌──────┬──┐               │ │ “新横浜” │ 3 │───────────────┘ └──────┴──┘



BohYoh.comトップページへ