アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 200906 実施分 問6
流れ図に従って,選択ソートによって値を大きい順に整列するとき,α 印の処理(比較)が実行される回数を表す式はどれか。
流れ図:
開始
→ ループ端「交換 i:1, 1, n-1」
→ 処理 i→k
→ ループ端「最大値 j:i+1, 1, n」
→ 判断 x(j):x(k) ← α 印(この比較の処理)。「>」のとき 処理 j→k を実行してループ端「最大値」の終わりへ。「≦」のときは j→k を飛ばして「最大値」の終わりへ
→ ループ端終わり「最大値」
→ 処理 x(k)→w; x(i)→x(k); w→x(i)
→ ループ端終わり「交換」
→ 終了
(注) ループ端の繰返し指定は,変数名:初期値,増分,終値 を示す。
答えを選ぶ
出典:基本情報技術者試験 科目A免除 修了試験 200906 実施分 問6(問題文は IPA の公開問題。解説は当サイト作成)
答えと解説を見る
正解:ア
覚える知識
選択ソートの比較回数
選択ソートの比較回数は入力の並びによらず n(n−1)/2 回である。
この問題で必要なこと
外側ループの i=1..n−1 ごとに内側ループで n−i 回比較するため、合計は (n−1)+…+1=n(n−1)/2。
ひっかけ
n(n−1) など、2 で割る前の値や、ループ範囲を 1 つずらした式を選ばせる。
この知識の出題:本試験系 0 回・免除試験 2 回(公開問題での観測値)