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

問題本文

従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率を a とする。

選択肢

• ア.(n+1) na / 2
• イ.(n+1) (1−a) / 2
• ウ.(n+1) (1−a) / 2 + n / 2
• エ.(n+1) (1−a) / 2 + na

正解

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

解説

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