線形探索法における平均比較回数の計算式

正解は エ です。 表に目的の従業員番号が存在する確率は $1 - a$、存在しない確率は $a$ です。 1. データが存在する場合（確率 $1 - a$）：$n$ 件のいずれかに等確率（$\frac{1}{n}$）で存在するため、先頭から線形探索したときの平均比較回数は $\frac{1 + 2 + \dots + n}{n} = \frac{n + 1}{2}$ 回となります。 2. データが存在しない場合（確率 $a$）：末尾まで探索して初めて見つからないことが確定するため、比較回数は必ず $n$ 回となります。 全体の平均比較回数はそれぞれの加重平均（期待値の和）となるため、次のようになります： $$\frac{(n + 1)(1 - a)}{2} + na$$ 場合 確率 比較回数 確率×回数 表にある 1−a 平均 (n＋1)/2 (n＋1)(1−a)/2 表にない a n（最後まで調べる） na 平均 (n＋1)(1−a)/2＋na

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

出典令和5年度 春期 応用情報技術者試験 午前 問6
ア
(n+1)na2\frac{(n+1)na}{2}
イ
(n+1)(1−a)2\frac{(n+1)(1-a)}{2}
ウ
(n+1)(1−a)2+n2\frac{(n+1)(1-a)}{2}+\frac{n}{2}
エ
(n+1)(1−a)2+na\frac{(n+1)(1-a)}{2}+na