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