平成26年 春期 応用情報技術者 午前 問6

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

 ア  
 イ  
 ウ  
 エ  


答え エ


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


キーワード
・線形探索法

キーワードの解説

戻る 一覧へ 次へ