平成26年度春期 応用情報技術者試験 午前 問6
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率をaとする。
- ア (n+1)/2 + na/2
- イ (n+1)(1−a)/2
- ウ (n+1)(1−a)/2 + n/2
- エ (n+1)(1−a)/2 + na
解答・解説を見る
正解：エ
AI解説
平均比較回数は「見つかる場合」と「見つからない場合」の期待値の和で求める。存在する場合(確率1−a),先頭から探して見つかるまでの平均比較回数は(1+2+…+n)/n=(n+1)/2回。存在しない場合(確率a)は表の全件と比較するのでn回。よって平均は(n+1)(1−a)/2+naとなる。 ア: 存在しない場合の比較回数をn/2としているが,存在しない場合は全n件と比較する必要があるため誤りである。 イ: 存在する場合の期待値のみで,存在しない場合(確率a)の比較回数naが抜けている。 ウ: 第2項がn/2×確率なしとなっており,存在しない確率aが掛けられていない点が誤りである。 エ: 正解。(見つかる場合の平均(n+1)/2)×確率(1−a)+(見つからない場合のn回)×確率aを合計した式である。 💡 線形探索の平均比較回数は「ヒット時(n+1)/2,ミス時n」が基本。確率付きの期待値問題は「各ケースの回数×そのケースの確率」を漏れなく足す,という形に持ち込めば機械的に解ける。
出典：平成26年度 春期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。