科目Bサンプル問題 [科目B]問3
問3
次のプログラム中のaとbに入れる正しい答えの組合せを，解答群の中から選べ。
手続 append は，引数で与えられた文字を単方向リストに追加する手続である。単方向リストの各要素は，クラス ListElement を用いて表現する。クラス ListElement の説明を図に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead は，単方向リストの先頭の要素の参照を格納する。リストが空のときは，listHead は未定義である。
〔プログラム〕
手続 append は，引数で与えられた文字を単方向リストに追加する手続である。単方向リストの各要素は，クラス ListElement を用いて表現する。クラス ListElement の説明を図に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead は，単方向リストの先頭の要素の参照を格納する。リストが空のときは，listHead は未定義である。
分類
アルゴリズムとプログラミング » データ構造及びアルゴリズム
正解
ア
解説
リスト構造は、隣接するデータ同士を参照（ポインタ）で連結して表現するデータ構造です。本問の単方向リストとは、下図のように最初の要素から最後の要素までが1方向に連結されたものです。
リスト構造では、要素を追加するには要素同士のつながりに途中で割り込む形となるため、要素を追加する際には、追加する要素の1つ前の参照を付け替える操作が必要となります。本問では、データ（val）と次の要素への参照（next）を持つ各要素を ListElement型 として定義しています。
〔aについて〕
プログラムでは、まずcurr ← ListElement(qVal)の部分で追加要素のListElementを作成しています。
その後空欄aを含む分岐に移り、条件式がtrueのときにはlistHead ← currを行っています。これは、追加する要素を変数 listHead（リストの先頭要素への参照）に設定する処理であり、これによりリストの先頭に追加要素が格納されることとなります。追加要素の格納位置をリストの先頭にすべきなのは、リスト内に要素がひとつもないときです。リストが空のときは、変数 listHead は初期値である"未定義の値"のままとなっているので、この処理を行うのは「listheadが未定義のとき」となります。したがって、空欄aに入るのは「未定義」が適切です。
〔bについて〕
前述のとおり、単方向リストへの要素追加では、先頭から順に末尾の要素までたどり、末尾要素の参照を追加する要素に書き換える必要があります。
else文はリスト内に要素が1つ以上存在するときの処理で、①while文を使って末尾の要素まで進める、②末尾要素の参照を書き換えるという2つの処理を行っています。while文では next の値が未定義でない間、prev を次の要素に進めていますが、これが①の処理となります。末尾の要素の next は未定義となっているので、末尾の要素に当たった時点でwhile文による繰返し処理は終了することになります。while文から抜けたとき、変数 prev には末尾の要素が格納されているので、その next（参照）には追加要素である「curr」を設定する処理が適切となります。参照の設定によりリストの末尾に追加要素が格納されます。
したがって「ア」の組合せが適切です。
〔aについて〕
プログラムでは、まずcurr ← ListElement(qVal)の部分で追加要素のListElementを作成しています。
その後空欄aを含む分岐に移り、条件式がtrueのときにはlistHead ← currを行っています。これは、追加する要素を変数 listHead（リストの先頭要素への参照）に設定する処理であり、これによりリストの先頭に追加要素が格納されることとなります。追加要素の格納位置をリストの先頭にすべきなのは、リスト内に要素がひとつもないときです。リストが空のときは、変数 listHead は初期値である"未定義の値"のままとなっているので、この処理を行うのは「listheadが未定義のとき」となります。したがって、空欄aに入るのは「未定義」が適切です。
〔bについて〕
前述のとおり、単方向リストへの要素追加では、先頭から順に末尾の要素までたどり、末尾要素の参照を追加する要素に書き換える必要があります。
else文はリスト内に要素が1つ以上存在するときの処理で、①while文を使って末尾の要素まで進める、②末尾要素の参照を書き換えるという2つの処理を行っています。while文では next の値が未定義でない間、prev を次の要素に進めていますが、これが①の処理となります。末尾の要素の next は未定義となっているので、末尾の要素に当たった時点でwhile文による繰返し処理は終了することになります。while文から抜けたとき、変数 prev には末尾の要素が格納されているので、その next（参照）には追加要素である「curr」を設定する処理が適切となります。参照の設定によりリストの末尾に追加要素が格納されます。
したがって「ア」の組合せが適切です。