従業員番号と氏名の対が 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である。
従って、平均比較回数は
(n＋1)／2 × (1−a) ＋ n × a
＝ (n＋1)(1−a)／2 ＋ na である。
| 問５ | 目次 | 問７ |