基本情報技術者令和5年[科目B]問3 整列プログラム

基本情報技術者令和5年 [科目B]問3

問3

次の記述中の　に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。

　次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで，first＜ last とする。手続 sort を sort(1，5) として呼び出すと，/*** α ***/ の行を最初に実行したときの出力は"　"となる。

〔プログラム〕

1 2 3 4 5
1 2 3 5 4
2 1 3 4 5
2 1 3 5 4

分類

アルゴリズムとプログラミング » データ構造及びアルゴリズム

正解

エ

解説

data = {2, 1, 3, 5, 4} に対して、sort(1, 5) を呼び出したときの処理をトレースしていきます。プログラム中のwhile (true)は、特定の条件式に依存せず、繰返し処理中で明示的に終了命令が出されたときのみ繰返し処理を中断する一般的な文です。

pivot ← (1 + 5) ÷ 2 の商 = 3
i ← first = 1
j ← last = 5
while (true) の繰返し処理に入る
//data[i] が pivot より小さい間、iに1を加えることを繰り返す
while (data[i] ＜ pivot)
　i ← i ＋ 1
endwhile
値が3より小さい data[1] と data[2] のとき、i が1→2、2→3と2回インクリメント（＋1）され、i=3 で繰返しが終了する
//data[j] が pivot より大きい間、jから1を減じることを繰り返す
while (pivot ＜ data[j])
　j ← j － 1
endwhile
値が3より大きい data[5] と data[4] のとき、j が5→4、4→3と2回デクリメント（－1）され、j=3 で繰返しが終了する
i ≧ j なので、while (true) の繰返し処理が終了する
/*** α ***/の処理が行われる

この時点で data = {2, 1, 3, 5, 4} と初期値と同じなので、先頭から順に出力すると、2 1 3 5 4 になります。したがって「エ」が正解となります。