応用情報技術者 2014年 秋期 午後 問03

解答の論理構成

1. ループ条件 ア
   • 【問題文】には「後者のポインタが連結リストの終わりに達するまでこの処理を繰り返す」とあります。
   • divideでは“後者”がbなので、“終わり”とはbがNULLになる瞬間です。
   • よってwhile文はbがまだNULLでない間だけ繰り返します。
   • すなわち ア = bがNULLと等しくない となります。
2. ループ内の2ステップ移動 イ
   • a は毎回1つ進めるために a ← a->next が置かれています。
   • b を2つ進めるためには、①ループ冒頭で b ← b->next、②その直後の if 文でさらに1回進める処理が必要です。
   • if文のガードは既に「bがNULLと等しくない」ですから、内部で行う追加1ステップが イ です。
   • よって イ = b ← b->next になります。
3. リストの切断位置 ウ
   • ループ終了時点でaは分割点（前半の最後のセル）を指しています。
   • p ← a->next で後半先頭を保存したあと、分割のために a->next を NULL に書き換えます。
   • したがって ウ = a->nextです。

誤りやすいポイント

• bとb->nextを混同する
  while ( b->next が NULL ではない ) とすると奇数要素リストで分割位置が一つ後ろにずれます。
• ループ内でbを2回進め忘れる
  イ を入れ忘れるとaとbの距離が1セルに縮まり、ほぼ中央になりません。
• 切断前にpを退避しない
  先に a->next ← NULL を実行すると後半先頭が失われ、戻り値が不正になります。

FAQ

解答の論理構成

1. 初期配置を確認
   • プログラム冒頭でa ← list、b ← a->nextなので、図3の先頭セル"6"を指すaと、その直後のセル"4"を指すbが用意されます。
   • 直後のif ( b が NULL と等しくない ) b ← b->nextにより、bはさらに一つ進み、セル"3"を指します。
2. ループ条件を把握
   • while行には「連結リストの終わりまで繰り返す」とあるため、アは「bがNULLと等しくない」すなわち bが末尾を過ぎていない ことを意味します。
   • ループ本体では
     a ← a->next b ← b->next if ( b が NULL と等しくない ) b ← b->next
     と記述されており、aは1セル、bは合計2セルずつ前進します。
3. 実際の前進を追跡
   連結リストの値列は図3より
   "6" → "4" → "3" → "8" → "7" → "2" → "1" → "5" です。

   ループ回数	aが指す値	bが指す値	ループ継続判定
   開始前	"6"	"3"	b ≠ NULL
   1回目終了	"4"	"7"	b ≠ NULL
   2回目終了	"3"	"1"	b ≠ NULL
   3回目終了	"8"	NULL	b ＝ NULL → ループ終了

4. α到達時の状態
   • whileループを抜けた直後（α位置）でaはセル"8"を指しています。
   • この時点でa->next（セル"7")を切り離すことで、前半リストが"6" "4" "3" "8"、後半リストが"7" "2" "1" "5"に分割されるしくみです。

誤りやすいポイント

• bの二重前進を見落として、aを1セル遅く数えてしまう。
• while条件を「b->nextがNULL」と誤解し、ループを1回余分または不足させる。
• 図3の値列を途中で読み違え、"7"と"8"の位置を取り違える。

FAQ

解答の導き方

誤りやすいポイント

• b の初期位置を誤解して「b は2番目を指す」としてしまう。図5 の「if ( bがNULLと等しくない )」「b ← b->next」を見落とすと誤りやすいです。
• ループ回数の数え方でoff-by-oneを起こす。特に条件付きのbの二回目の移動が何回実行されるか（$k$ 回か $k-1$ 回か）を間違えると答えを間違えます。
• 小さいケース（$N=0$ や $N=1$）を確認せずに一般式を決めてしまい、境界での動作を誤る。$N=0$（1個のとき）は前半1、後半0になります。
• 「前半と後半は常に同数になる」と思い込み、奇数個のときの中央の扱いを忘れる。

FAQ

解答の論理構成

1. 併合ループの継続条件
   図7には
   while ( エ 、かつ、bが NULL と等しくない )
   とあります。ここでbについては既に “bがNULLと等しくない” が書かれているので、残る エ にはaが空でないことを示す条件を入れれば、両方のリストに要素がある間ループします。
   ➡ エ ＝ 「aがNULLと等しくない」
2. 残余リストの判定
   ループを抜けると、どちらかのリストが空になっています。図7の
   if ( オ ) // 要素が残っている連結リストを連結する
   は“どちらに要素が残っているか”を判定する式です。
   ・aが空ならbに要素が残る
   ・逆にbが空ならaに要素が残る
   よって
   • 「aがNULLと等しい」
   • または同値の 「bがNULLと等しくない」
     のいずれでも正しく動作します。
     ➡ オ ＝ 「aがNULLと等しい」（同値条件として「bがNULLと等しくない」も可）
3. 返却値
   ダミーセルheadを使っているため、完成した連結リストの実際の先頭はhead->nextです。図7の
   return カ
   に入るのはhead->nextになります。
   ➡ カ ＝ head->next

誤りやすいポイント

• ダミーセルを使う場合、返却時にheadをそのまま戻してしまうミス。
• オ で “要素が残っている方”を判定するのにaがNULLと等しくない と書いてしまい、条件が逆になるミス。
• while条件にaとbの両方を同時に書き、二重否定で混乱してループが早く終わるロジックエラー。

FAQ

解答の導き方

1. アルゴリズムの振る舞いの確認
   問題文に「ここでは、それぞれの要素数が1になるまでデータ列の分割を繰り返し」とあり、分割は要素数が1の単位まで行われます。したがって最終的に得られる単位リスト（葉）の数は入力要素数と一致し、今回なら葉の数は32です。
2. 再帰呼び出しを木構造で考える
   マージソート全体の再帰呼び出しを根付き二分木（以下、再帰木）で表すと、各ノードはある部分列に対するマージソート呼び出しを表します。図2の(2)に「分割する」とあり、要素数が2以上の呼び出しは必ず前半と後半の二つの再帰呼び出しを行います。図2の(4)に「前半と後半の二つのマージソート済みデータ列を…併合する」とあるように、戻ってくる際に併合（merge）が実行されます。つまり再帰木の葉は分割の終端（要素数1の呼び出し）であり、内部ノード（非葉）は併合を行う呼び出しに対応します。
3. 木の性質から併合回数を求める（形式的導出）
   以下を定義します。葉の数を $L$、内部ノード（＝併合を行う呼び出し）の数を $I$、全ノード数を $N$ とします。明らかに $N=I+L$ です。
   根付き木の辺（親→子の接続）の総数は常に $N-1$ ですから辺の数を $E$ とすると $E=N-1$ です。
   本問題の再帰木では、内部ノードは分割時に必ず二つの子を生成するため、全辺数は内部ノードが持つ子辺の総和で表せます。したがって $E=2I$ です。
   以上を合わせると $2I=(I+L)-1$
   となり整理すると $I=L-1$
   が得られます。今回 $L=32$ なので $I=32-1=31$、つまりmergeの呼び出し回数は31回です。
4. 直感的な確認（別解）
   分割が終わると32個の単独リストができ、各mergeは二つのリストを一つにまとめるのでリストの総数は1回のmergeでちょうど1つ減ります。32個を1個にするには32−1＝31回のmergeが必要、という直感的な確認も成り立ちます。

誤りやすいポイント

• 二分木の扱いで「辺」と「内部ノード」を混同する
  「辺の数 = ノード数 − 1」という一般事実と「内部ノードと葉の関係」を正しく区別する必要があります。本問では内部ノード数 $I$ と葉数 $L$ の関係は $I=L-1$ です（導出は本文参照）。
• merge回数を比較回数や計算量 $O(n\log n)$ と混同する
  mergeの呼び出し回数は $n-1$（ここで $n$ は要素数）であり、比較回数や実行時間のオーダー（$O(n\log n)$）とは別物です。両者を取り違えると誤答になります。
• 分割の終端条件を誤解する
  問題文が明示する「要素数が1になるまで」の分割を見落とすと葉数の数え方を誤ります。分割の終端条件が変われば答えも変わる点に注意してください。
• ノードの子数を過小評価する誤り
  要素数が奇数の場合などに「片方の再帰呼び出しが空になる」と考えてしまうと内部ノードの子数が2でないと誤認することがありますが、本アルゴリズムの分割ルールでは要素数が2以上であれば両方に少なくとも1要素が入るため、内部ノードは常に2子です。
• $n$ が2のべき乗でない場合の誤解
  再帰木が完全二分木でなくても、内部ノードは常に2子であるため $I=L-1$ は一般に成立します。2のべき乗でないと特別扱いが必要、と考えるのは誤りです。

FAQ