本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

令和5年度 春期 応用情報技術者試験問題と解説

問6

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

ア (n+1)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 である。

問5 目次 問7