2023年 春期 応用情報技術者 午前 問6

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

 ア    イ  
 ウ    エ  


答え エ


解説
検索する従業員番号が表に存在する場合、線形探索法を用いると比較回数は
 (n + 1)/2 …(1)
になる。
また、存在しない場合の比較回数は
 n …(1)
である。
ここで、検索する従業員番号が表に存在しない確率がaであり、存在する確率が(1 - a)であるから、平均比較回数は
 
(エ)になる。


キーワード
・線形探索法

キーワードの解説
  • 線形探索法
    データの状態にかかわらず採用することができる探索方法で、探索するデータの先頭から順に、探索する値と一致するかを比較していきます。
    整列済み、未整列にかかわらず探索可能ですが、整列済みのデータの場合は2分探索法に比べ時間がかかります。

もっと、「線形探索法」について調べてみよう。

戻る 一覧へ 次へ