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