問題プレビューID: 90be87f3基本情報技術者試験 午前免除試験 2009年6月

問 6
基本情報技術者試験 午前免除試験 2009年6月

流れ図に従って,選択ソートによって値を大きい順に整列するとき,α 印の処理(比較)が実行される回数を表す式はどれか。

(注) ループ端の繰返し指定は,変数名:初期値,増分,終値を示す。

解説

正解は「ア」です。

外側のループは ii を 11 から n−1n - 1 まで動かし,各 ii について内側のループで jj を i+1i + 1 から nn まで動かしながら,暫定最大値 x(k)x(k) と x(j)x(j) を比較する(α 印の処理)。

内側のループの比較回数は,jj が i+1i + 1 から nn までの n−in - i 回である。これを i=1i = 1 から n−1n - 1 まで合計すると,

(n−1)+(n−2)+⋯+1=n(n−1)2(n - 1) + (n - 2) + \cdots + 1 = \frac{n(n - 1)}{2}

となる。したがって,比較は n(n−1)2\dfrac{n(n - 1)}{2} 回実行され,正解は「ア」です。

  • イ・エ: n(n−1)n(n - 1) や n(n+1)n(n + 1) は比較回数として過大である。
  • ウ: n(n+1)2\dfrac{n(n + 1)}{2} は 11 から nn までの和であり,比較回数とは一致しない。

関連問題

本文が同じ・似ている問題を表示しています