アルゴリズムとプログラミング

基本情報技術者試験 科目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 回(公開問題での観測値)

この知識をアプリで解いて覚える レッスン「整列(ソート)アルゴリズムの比較」で学ぶ

同じ知識の過去問