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

正解

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

正答率 67.4%（731人中 493人が正解）

問題の解説

表に従業員番号がある場合は、先頭から順に比較して 1〜n 回目のどこかで見つかるので、平均は (n+1)/2 回になる。ない場合は n 件すべてを比較するので n 回かかる。存在する確率が 1−a、しない確率が a なので、平均比較回数は である。

選択肢ごとの解説

• アa = 0 のときに 0 回となり、必ず存在する場合の (n+1)/2 回と合わない。
• イ見つかる場合の項だけで、見つからない場合の n 回の比較が含まれていない。a = 1 のときに 0 回になってしまう。
• ウ存在しない場合の項が確率 a に関係なく n/2 になっている。a = 0 のとき (n+1)/2 + n/2 となり、必ず存在する場合の (n+1)/2 を超える。
• エ正しい。見つかる場合は平均 (n+1)/2 回、見つからない場合は n 回なので、確率で重み付けすると (n+1)(1−a)/2 + na になる。