応用情報技術者試験 応用情報技術者試験 令和5年度春期 午前 問6: 従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここ

正解

エ. (n+1) (1−a) / 2 + na

正答率 67.5%（729人中 492人が正解）

問題の解説

線形探索の平均比較回数は「見つかる場合」と「見つからない場合」を確率で重み付けして足し合わせて求めます。表に存在する確率は (1−a) で、存在する場合はどの位置にあるかが一様なので平均比較回数は (1+n)/2＝(n+1)/2 回です。存在しない確率は a で、その場合は末尾まで調べるので n 回比較します。よって全体の平均比較回数は (n+1)/2 ×(1−a) ＋ n×a となり、選択肢エが正解です。見つからない場合の比較回数を (n+1)/2 と混同すると誤った式（ウなど）を選んでしまう点に注意します。