従業員番号と氏名の対がn 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。
この処理における平均比較回数を求める式はどれか。
ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。
また、与えられた従業員番号がこの表に存在しない確率をa とする。
ア | |
イ | |
ウ | |
エ |
答え エ
【解説】
検索する従業員番号が表に存在する場合、線形探索法を用いると比較回数は
(n +1)/2 …(1)
になる。
また、存在しない場合の比較回数は
n …(1)
である。
ここで、検索する従業員番号が表に存在しない確率がa であり、存在する確率が(1-a )であるから、平均比較回数は
(エ)になる。
【キーワード】
・線形探索法