問題
従業員番号と氏名の組が n 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率を a とする。
選択肢
- 1(n+1)/2 + na/2
- 2(n+1)(1-a)/2
- 3(n+1)(1-a)/2 + n/2
- 4(n+1)(1-a)/2 + na
正解
4. (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 が全体の平均比較回数である。（出典: 平成26年度 春期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習