平成26年秋期試験午後問題　問3

問3　プログラミング

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

設問1

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

解答例・解答の要点

  • ア：bがNULLと等しくない
    イ：b ← b->next
    ウ：a->next
  • 8
  • 前半：N＋1
    後半：N

解説

  • 〔アについて〕
    問題文の〔連結リストの分割〕には、「後者のポインタが連結リストの終わりに達するまでこの処理を繰り返す」とあります。さらに、[ア]が含まれる8行目のコメントには、「連結リストの終わりまで繰り返す」とあります。このことから、[ア]には連結リストの終わりまで処理を繰り返すための継続条件が入るとわかります。

    「連結リストの終わり」とは、「次のセルへのポインタを示すメンバnextがNULLである状態」のことです。すなわち、2つずつ進む後者のnextがNULLではない間だけ、処理を繰り返せば良いことになります。図5の5行目を見ると、b だけ余分に1つポインタを先に進めていることから、b が2つずつ進む後者のポインタに相当するとわかります。

    よって、[ア]には「bがNULLと等しくない」が入ります。

    ∴ア＝bがNULLと等しくない

    〔イについて〕
    問題文の〔連結リストの分割〕には、「連結リストをセルの個数がほぼ同じになるように分割するために，ポインタ変数を二つ用意し，一方が一つ進むごとに，他方を二つずつ進める。」とあります。前述しましたが、二つのポインタとは変数aと変数bのことであり、a を一つずつ進め、b を二つずつ進めています。

    問題文の〔連結リストの分割〕に、「後者のポインタが連結リストの終わりに達するまでこの処理を繰り返すと、前者のポインタは連結リストのほぼ中央のセルを指す。」とあるので、後者のポインタ（b）が連結リストの終わりに達するまで、b を二つずつ進める処理が必要です。10行目・11行目で a と b を一つ進めているため、[イ]で b だけをもう一つ進める必要があります。

    ポインタを先に進めるには、次のセルへの参照を b に代入すれば良いので、[イ]には「b ← b->next」が入ります。

    ∴イ＝b ← b->next

    〔ウについて〕
    [ウ]を含む後半3行は、whileループを抜けた後に実行されるので、b がリストの終端に達した後の処理となります。
    問題文の〔連結リストの分割〕には、「後者のポインタが連結リストの終わりに達するまでこの処理を繰り返すと、前者のポインタは連結リストのほぼ中央のセルを指す。」とあります。a は一つずつ、b は二つずつ進めるのですから、b がリストの終端に達した時点で a はリストのちょうど中央のセルを参照しているはずです。図4「連結リストの分割後のイメージ」の中では、[16]のセルが a の位置です。

    図4からもわかるように、連結リストの分割は、分割後の連結リストのうち、前半の連結リストの最後のセルのメンバ next をNULLにすることで行います（後半リストとの連結を断ち切る）。つまり、a の次のセルのポインタである next にNULLを代入しなければなりません。よって、[ウ]には「a->next」が入ります。

    ∴ウ＝a->next

  • 繰り返しになりますが、変数aは一つずつ、変数bは二つずつ進みます。図3の連結リストに対して関数 divide を実行すると、b が終端の8番目のセルに達した時点で、a は半分の4番目のセルを参照しているはずです。先頭から4番目のセルのメンバ value の値は「8」です。

    ∴8

  • 連結リストのセルの個数が奇数のときに、関数 divide を実行した場合の前半と後半の連結リストのセルの個数を考えます。偶数（2N）では必ず半分のNの位置に a が来ますが奇数ではどうなるでしょうか。

    プログラムの11・12行目を見ると、一つ進んだ時点で b がNULLのときには2回目の進みが行われないことがわかります。
    if (bがNULLと等しくない)
    　b ← b->next（イの答え）
    つまり、リストの大きさが5ならば{a=3、b=5}、リストの大きさが9ならば{a=5、b=9}というような状態でwhileループが終了します。a の位置から前の要素が前半リストとなるため、大きさ5の場合には前半が3つで後半は2つ、大きさ9の場合には前半が5つで後半は4つというように分割されます。これをNを使って一般化すると、前半の連結リストのセルの数はN+1個、後半の連結リストのセルの数はN個となります。
    • 2N+1＝5、N＝2、前半3個＝N+1個、後半2個＝N個
    • 2N+1＝9、N＝4、前半5個＝N+1個、後半4個＝N個
    よって、前半の個数は「N+1」、後半の個数は「N」が正解です。

    ∴前半＝N+1、後半＝N
広告

設問2

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

解答例・解答の要点

エ：aがNULLと等しくない
オ：・aがNULLと等しい
・bがNULLと等しくない
カ：head->next

解説

〔エについて〕
プログラムの7行目～15行目では、a->value と b->value を比較して、小さい方をpに追加する処理を行っています。そのため、この処理が適切に処理されるためには a と b の両方の連結リストにセルが残っている必要があります。すなわち「aとbの両方がNULLではない」場合に行う処理です。
よって、[エ]には「aがNULLと等しくない」が入ります。

∴エ＝aがNULLと等しくない

〔オについて〕
プログラムの6行目のwhile文の継続条件式が「aがNULLと等しくない、かつ、bがNULLと等しくない」であるため、18行目以降は「aとbの少なくとも一方がNULLとなった」…つまり、リストの終端に達した際に行う処理です。

図6とプログラムを見ながら併合動作を確認すると、どちらかのリストが終端に達した場合には、もう一方のリストの要素を現状の順番のまま p の後ろに連結させることがわかります（併合前の部分リストは整列済みのため）。すなわち、a がNULLのときには b を p の後ろに連結させ、b がNULLのときには a を p の後ろに連結させる処理が必要です。

[オ]が真のときには、p->next ← b で、b を p の後ろに連結されていますが、これは a がNULLのときに行うべき処理です。よって、[オ]には「aがNULLと等しい」または「bがNULLと等しくない」が入ります。

∴オ＝aがNULLと等しい、または、bがNULLと等しくない

〔カについて〕
関数 merge の戻り値が入ります。戻り値については、問題文の〔連結リストの併合〕に、「併合後の連結リストへの先頭へのポインタを戻り値とする。」とあるので、先頭へのポインタを示す式を考えます。

図6「連結リストの併合の流れ」でリストの先頭を指すポインタが head になっていること、及びプログラム中でダミーのセル head の後ろに p を連結していることから、ポインタ変数 head のメンバ next が指すセルが、併合後の連結リストの先頭であることがわかります。よって、[カ]には「head->next」が入ります。

∴カ＝head->next
広告

設問3

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

解答例・解答の要点

31

解説

32個のセルから成る連結リストに対して、図2のアルゴリズムに相当するプログラムを実行した場合、(1)～(3)が実行されることで各1個のセルを持つ32つのリストに分割されます。

マージソートでは隣り合ったリスト同士を整列しながら併合していくことを繰り返します。併合は次のように進んでいきます。
  • 1要素×32リストを2つの要素を持つ16つのリストにする。ここで関数 merge が16回呼び出される。
  • 2要素×16リストを4つの要素を持つ8つのリストにする。ここで関数 merge が8回呼び出される。
  • 4要素×8リストを8つの要素を持つ4つのリストにする。ここで関数 merge が4回呼び出される。
  • 8要素×4リストを16つの要素を持つ2つのリストにする。ここで関数 merge が2回呼び出される。
  • 16要素×2リストを32つの要素を持つ1つのリストにして、併合完了。ここで関数 merge が1回呼び出される。
よって、関数 merge が1回呼び出される回数は、

　16＋8＋4＋2＋1＝31回

∴31
広告
模範解答

前の問題次の問題

▲
Pagetop