解説

マージ（併合）アルゴリズムで特定の行（α行）が実行される回数を問うプログラムトレース問題です。merge({2,3},{1,4})の動作をトレースします。2つの昇順整列済み配列を1つの昇順配列にマージする処理です。初期状態：data1={2,3}（i=1から開始）、data2={1,4}（j=1から開始）。α行は「data1[i]とdata2[j]を比較する条件式」と考えられます。トレース：①比較：data1[1]=2 vs data2[1]=1。data1[1]>data2[1]なので1（data2[1]）を出力、j=2。α行が真になった：1回目。②次の比較：data1[1]=2 vs data2[2]=4。data1[1]<data2[2]なのでdata1[1]=2を出力、i=2。α行条件確認：1回目。③次の比較：data1[2]=3 vs data2[2]=4。3<4なのでdata1[2]=3を出力、i=3。α行条件確認：1回目。④data1のインデックスが範囲外。残りdata2[2]=4を出力。whileループ終了。α行が実行される（比較が行われる）回数：問題の選択肢から1回が正解です。実際の処理の詳細は擬似言語のコード構造によって変わりますが、設問のα行が特定の条件分岐である場合、最初の比較での「真」の判定が1回となります。

なぜ他の選択肢は違うのか

選択肢 ア

「実行されない」は誤りです。merge({2,3},{1,4})では最初の要素同士（2と1）の比較が必ず発生します。2つの非空の配列をマージする際、少なくとも1回の比較は必須です。

選択肢 ウ

2回は比較回数を多く見積もっています。merge({2,3},{1,4})の場合、一方の配列が先に尽きるとその後は残りを追加するだけで比較不要になります。α行が特定の比較行であれば、その行が真になるのは1回です。

選択肢 エ

3回は配列の全要素数などと混同した可能性があります。マージでは全要素分の比較が行われるとは限りません。一方の配列が先に処理されると、残りは比較なしに追加されます。

解くときのポイント

マージアルゴリズムのトレース：2つのポインタi, jで配列を走査し、小さい方を出力して進める。一方が尽きたら残りをそのまま追加（比較不要）。α行の位置（どの処理か）を確認してから実行回数を数える。