修了試験 2012-01-22実施分 基本情報技術者試験 問50

解説

正解は2です。 処理区分を順に判定していくとき、比較回数は判定の順番によって変わります。 よく出現する区分ほど早く判定すれば、少ない比較で処理区分が決まるデータが多くなります。 【計算】 例として、区分Xの出現比率が70％、区分Yが20％、区分Zが10％とします。 Xから順に判定すると、平均比較回数は1×0.7＋2×0.2＋2×0.1＝1.3回です。 Zから順に判定すると、平均比較回数は1×0.1＋2×0.2＋2×0.7＝1.9回です。 出現比率の大きい区分から判定する方が、比較回数は少なくなります。 【選択肢別解説】 1：× 出現比率が中間の区分を先にすると、最も多いデータの判定が後回しになります。 全体の比較回数は最小になりません。 2：○ 出現比率が最も大きい区分から判定すると、多くのデータが少ない比較回数で判定できます。 そのため全体の比較回数が少なくなります。 3：× 出現比率が最も小さい区分から判定すると、大部分のデータが何度も比較されます。 全体の比較回数はむしろ多くなります。 4：× 上の計算例のとおり、判定の順番によって全体の比較回数は変わります。 【ポイント】 平均比較回数は「各区分の比較回数×出現比率」の合計で求めます。 出現頻度の高いものを先に調べるのは、プログラムの効率化の基本的な考え方です。