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

• 【問題文】には「後者のポインタが連結リストの終わりに達するまでこの処理を繰り返す」とあります。
• divide では“後者”が b なので、“終わり”とは b が NULL になる瞬間です。
• よって while 文は b がまだ NULL でない間だけ繰り返します。
• すなわち ア = bがNULLと等しくない となります。

• a は毎回1つ進めるために a ← a->next が置かれています。
• b を2つ進めるためには、①ループ冒頭で b ← b->next、②その直後の if 文でさらに1回進める処理が必要です。
• if 文のガードは既に「b が NULL と等しくない」ですから、内部で行う追加1ステップが イ です。
• よって イ = b ← b->next になります。

• ループ終了時点で a は分割点（前半の最後のセル）を指しています。
• p ← a->next で後半先頭を保存したあと、分割のために a->next を NULL に書き換えます。
• したがって ウ = a->next です。

• プログラム冒頭でa ← list、b ← a->nextなので、図3の先頭セル"6"を指すaと、その直後のセル"4"を指すbが用意されます。
• 直後のif ( b が NULL と等しくない ) b ← b->nextにより、bはさらに一つ進み、セル"3"を指します。

• while 行には「連結リストの終わりまで繰り返す」とあるため、アは「b が NULL と等しくない」すなわち b が末尾を過ぎていない ことを意味します。
• ループ本体では
  a ← a->next b ← b->next if ( b が NULL と等しくない ) b ← b->next
  と記述されており、aは1セル、bは合計2セルずつ前進します。

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

「一方が一つ進むごとに、他方を二つずつ進める」
と説明しています。一つずつ進むポインタを slow、二つずつ進むポインタを fast と呼びます。

• fast の移動回数 … $2N$ 回
• slow の移動回数 … $N$ 回
  よって slow は先頭から $N$ 個進んだセル（0 始まりならインデックス $N$）を指します。

• 先頭から slow まで … $N+1$ 個（slow を含む）
• 残り … $2N+1-(N+1)=N$ 個
  したがって
  前半：$N+1$ 後半：$N$
  が求まります。

• 「aが NULL と等しい」
• または同値の 「bが NULL と等しくない」
  のいずれでも正しく動作します。
  ➡ オ ＝ 「aが NULL と等しい」（同値条件として「bが NULL と等しくない」も可）

• 葉数を $n$ とすると、二分木の辺数は $n-1$（根から葉まで張られる）。
• 各内部ノードは必ず一度だけ併合（“図2中の(4)”＝merge 呼び出し）を担当する。
• したがって merge の呼び出し回数は $n-1$。