令和5年度 春期 応用情報技術者試験 午前 問6
従業員番号と氏名の対がn件格納されている表に線形探索法を用いて，与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで，検索する従業員番号はランダムに出現し，探索は常に表の先頭から行う。また，与えられた従業員番号がこの表に存在しない確率をaとする。
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：エ
線形探索法では、次の2つのケースがあります。
-
データが存在する場合
ランダムに探索するため、データの発見までに平均 (n+1)/2 回の比較が必要です。データが存在する確率は (1-a) です。 -
データが存在しない場合
データが存在しない場合、すべてのデータを比較するため比較回数は n になります。データが存在しない確率は a です。
これらを合わせた平均比較回数は以下のようになります：
平均比較回数 = ( (n+1)/2 ) × (1-a) + n × a
この式に最も合致するのは エ です。
答え
エ: (n+1)(1-a) / 2 + na
出典：令和5年度 春期 応用情報技術者試験 午前 問6
