BohYoh.com《基本情報技術者試験》2006年度＝平成18年度・秋期午前問13

基本情報技術者試験

2006年度＝平成18年度・秋期

午前

問13

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

　　　　　　　　　　　列　　　　　　　Ａ　　　　１　　　　２　　　　　　┌──────┬──┐ 　　　１　│　“東京”　│ ２ │ 　　　　　├──────┼──┤ 行　　２　│　“品川”　│ ３ │ 　　　　　├──────┼──┤ 　　　３　│ “名古屋” │ ４ │ 　　　　　├──────┼──┤ 　　　４　│ “新大阪” │ ０ │ 　　　　　├──────┼──┤ 　　　５　│ “新横浜” │　　│ 　　　　　└──────┴──┘

	第１の操作	第２の操作
ア	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)

解答

ウ

解説

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

　１　　　　　　　　　　　２　　　　　　　　　　　３　　　　　　　　　　　４ ┌──────┬──┐　┌──────┬──┐　┌──────┬──┐　┌──────┬──┐ │　“東京”　│ ２ │→│　“品川”　│ ３ │→│ “名古屋” │ ４ │→│ “新大阪” │ ０ │ └──────┴──┘　└──────┴──┘　└──────┴──┘　└──────┴──┘ 　５ ┌──────┬──┐ │ “新横浜” │　　│　　※リスト内には含まれず独立しています。 └──────┴──┘

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

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

　１　　　　　　　　　　　２　　　　　　　　　　　３　　　　　　　　　　　４ ┌──────┬──┐　┌──────┬──┐　┌──────┬──┐　┌──────┬──┐ │　“東京”　│ ２ │→│　“品川”　│ ３ │→│ “名古屋” │ ４ │→│ “新大阪” │ ０ │ └──────┴──┘　└──────┴──┘　└──────┴──┘　└──────┴──┘ 　　　　　　　　　　　　　　　　　　　　　　　　　　↑ 　５　　　　　　　　　　　　　　　　　　　　　　　　│ ┌──────┬──┐　　　　　　　　　　　　　　　│ │ “新横浜” │ ３ │───────────────┘ └──────┴──┘

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

　１　　　　　　　　　　　２　　　　　　　　　　　３　　　　　　　　　　　４ ┌──────┬──┐　┌──────┬──┐　┌──────┬──┐　┌──────┬──┐ │　“東京”　│ ５ │　│　“品川”　│ ３ │→│ “名古屋” │ ４ │→│ “新大阪” │ ０ │ └──────┴──┘　└──────┴──┘　└──────┴──┘　└──────┴──┘ 　　　　　　　　 │ 　　　　　　　　　　　　　　　　↑ 　５　　　　　　 ↓ 　　　　　　　　　　　　　　　　│ ┌──────┬──┐　　　　　　　　　　　　　　　│ │ “新横浜” │ ３ │───────────────┘ └──────┴──┘