従業員番号と氏名の対がn件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。
この処理における平均比較回数を求める式はどれか。
ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。
また、与えられた従業員番号がこの表に存在しない確率をaとする。
| ア |  |
イ |  |
|
| ウ |  |
エ |  |
答え エ
【解説】
検索する従業員番号が表に存在する場合、線形探索法を用いると比較回数は
(n + 1)/2 …(1)
になる。
また、存在しない場合の比較回数は
n …(1)
である。
ここで、検索する従業員番号が表に存在しない確率がaであり、存在する確率が(1 - a)であるから、平均比較回数は
(エ)になる。
【キーワード】
・線形探索法
- 線形探索法
データの状態にかかわらず採用することができる探索方法で、探索するデータの先頭から順に、探索する値と一致するかを比較していきます。
整列済み、未整列にかかわらず探索可能ですが、整列済みのデータの場合は2分探索法に比べ時間がかかります。
もっと、「線形探索法」について調べてみよう。
戻る
一覧へ
次へ