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

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