修了試験 2011-06-26実施分 基本情報技術者試験 問7

解説

正解は1です。 この問題は、選択ソートで比較が何回行われるかを、流れ図のループ構造から求める問題です。 流れ図では、外側のループ「交換」がiを1から1ずつ増やしてn－1まで繰り返します。 内側のループ「最大値」は、jをi＋1から1ずつ増やしてnまで繰り返します。 α印の比較x(j)：x(k)は内側のループの中にあるので、内側ループの繰返し回数の合計が答えです。 内側ループでは、より大きい値が見つかるとkを更新し、ループ終了後にx(k)とx(i)を交換します。 【計算】 i＝1のとき、jは2〜nなので比較はn－1回です。 i＝2のとき、jは3〜nなので比較はn－2回です。 i＝n－1のとき、jはnだけなので比較は1回です。 合計は(n－1)＋(n－2)＋…＋1＝n(n－1)/2回です。 【選択肢別解説】 1：○ 内側ループの回数n－iをi＝1からn－1まで合計すると、n(n－1)/2になります。 2：× n(n－1)は正しい回数の2倍です。 jはi＋1から始まるので、同じ組の比較を2回することはありません。 3：× n(n＋1)/2は1からnまでの和です。 外側ループはn－1回、内側ループは最大n－1回なので、正しくはn(n－1)/2です。 4：× n(n＋1)は1からnまでの和の2倍であり、比較回数を過大に数えています。 【ポイント】 選択ソートの比較回数はデータの並び方に関係なく常にn(n－1)/2回で、計算量はO(n²)です。 バブルソートの比較回数も、基本形では同じくn(n－1)/2回です。