平成26年度 春期
応用情報技術者試験問題と解答
問6
従業員番号と氏名の対が n 件格納されている表に
線形探索法を用いて、与えられた従業員番号から
氏名を検索する。この処理における平均比較回数を
求める式はどれか。ここで、検索する従業員番号は
ランダムに出現し、探索は常に表の先頭から行う。
また、与えられた従業員番号がこの表に存在しない
確率を a とする。

 ア (n+1)/2 + na/2
 イ (n+1)(1−a)/2
 ウ (n+1)(1−a)/2 + n/2
 エ (n+1)(1−a)/2 + na



【正解】 エ

線形検索法は最初から順番に検索していく方法である。

検索する従業員番号が表に存在する場合の平均比較回数は
(n+1)/2 であり、
検索する従業員番号が表に存在する場合の比較回数は常に
である。

従って、平均比較回数は
(n+1)/2 × (1−a) + n × a
(n+1)(1−a)/2 + na である。

EXCEL VBAのご相談なら ファーストマクロ 



問5 目次 問7
ファーストマクロ TOPページ