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

解説　本サイト独自（IPA公表のものではありません）

エ　平均比較回数は，各場合の比較回数をその発生確率で重み付けした値である。表に存在する確率は1－aで，位置はランダムなので比較回数の平均は（n＋1）÷2となる。存在しない確率はaで全n件を比較するため，両者の和は（n＋1）（1－a）÷2＋naとなる。

• ア　存在しない場合の比較回数はnであり，その寄与はnaである。（n＋1）na÷2とすると，位置の平均まで余分に掛けている。
• イ　表に存在する場合の平均比較回数だけを確率で重み付けした式であり，存在しない場合に全n件を比較する分が含まれていない。
• ウ　存在しない場合の寄与を，確率aに関係なくn÷2として加えている。存在しない確率がaなので，この部分はnaでなければならない。