アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20120122 実施分 問50
売上ファイルのレコードの項目の一つに処理区分があり，この処理区分に応じた処理をしたい。全売上データに対する各処理区分の出現比率はあらかじめ分かっている。処理区分を判定するための比較回数に関する記述のうち，適切なものはどれか。
- ア 出現比率が中間の処理区分のものを先に判定すると，全体の比較回数が少なくなる。
- イ 出現比率が最も大きい処理区分から先に判定すると，全体の比較回数が少なくなる。
- ウ 出現比率が最も小さい処理区分から先に判定すると，全体の比較回数が少なくなる。
- エ どのような順番でも全体の比較回数は同じである。
出典：基本情報技術者試験 科目A免除 修了試験 20120122 実施分 問50
答えと解説を見る
正解：イ
覚える知識
線形探索の比較回数最小化(出現頻度順)
逐次判定では、出現頻度の高いものから順に判定すると平均比較回数が最小になる。
この問題で必要なこと
出現比率の大きい区分から順に判定すると平均比較回数が最小になる。
ひっかけ
最小の比率や中間から先に判定するのは非効率。
この知識の出題：本試験系 0 回・免除試験 2 回（公開問題での観測値）