応用情報技術者 試験情報＆徹底解説

マージソートに関する次の記述を読んで，設問1～3に答えよ。

　マージソートは，整列(ソート)したいデータ(要素)列を，細かく分割した後に，併合(マージ)を繰り返して全体を整列する方法である。
　ここでは，それぞれの要素数が1になるまでデータ列の分割を繰り返し，分割されたデータ列を昇順に並ぶように併合していくアルゴリズムを考える。例として，要素数が8の場合のアルゴリズムの流れを図1に示す。　再帰呼出しを使って記述したマージソートのアルゴリズムを図2に示す。　図2のアルゴリズムを連結リストに対して実行するプログラムを考える。ここでは，整列対象のデータとして正の整数を考える。連結リストは，複数のセルによって構成される。セルは，正の整数値を示すメンバー value と，次のセルへのポインタを示すメンバー next によって構成される。連結リストの最後のセルの next の値は，NULLである。連結リストのデータ構造を図3に示す。〔連結リストの分割〕
　図2中の(2)の処理を行う関数 divide を考える。関数 divide は，連結リストの先頭へのポインタ変数 list を引数とし，分割後の後半の連結リストの先頭へのポインタを戻り値とする。連結リストの分割前後のイメージを図4に示す。　連結リストをセルの個数がほぼ同じになるように分割するために，ポインタ変数を二つ用意し，一方が一つ進むごとに，他方を二つずつ進める。後者のポインタが連結リストの終わりに達するまでこの処理を繰り返すと，前者のポインタは連結リストのほぼ中央のセルを指す。この方法を利用した関数 divide のプログラムを図5に示す。以下，連結リストのセルを指すポインタ変数を a とするとき，aが指すセルのメンバー value を a->value と表記する。〔連結リストの併合〕
　図2中の(4)の処理を行う関数 merge を考える。関数 merge は，二つの連結リストの先頭へのポインタ変数 a と b を引数とし，併合後の連結リストへの先頭へのポインタを戻り値とする。併合処理を行う際には，ダミーのセルを用意し(そのセルへのポインタを head とする)，この後ろに併合後の連結リストを構成する。a と b が指すセルの値を比較しながら，値が小さい順に並ぶよう処理を進める。連結リストの併合の流れを図6(処理は，①，②，③，…と続く)に，関数 merge のプログラムを図7に示す。

〔連結リストの分割〕について，(1)～(3)に答えよ。

• 図5中のア～ウに入れる適切な字句を答えよ。
• 図3の連結リストに対して関数 divide を実行し，プログラムが図5中のαの部分に達したとき，ポインタ変数 a は，図3中のどのセルを指しているか。指しているセルの値(valueの数値)を答えよ。
• 奇数 2N＋1 個のセルから成る連結リストを関数 divide で分割すると，前半と後半の連結リストのセルの個数はそれぞれ幾つになるか式で答えよ。

図7中のエ～カに入れる適切な字句を答えよ。

32個のセルから成る連結リストに対し，図2のアルゴリズムに相当するプログラムを実行した場合，関数 merge は何回呼び出されるか答えよ。