問題
従業員番号と氏名の対が n 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。また、与えられた従業員番号がこの表に存在しない確率を a とする。
選択肢
- 1(n＋1)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、存在しない場合（確率 a）は最後まで調べるので n 回となる。期待値は (1−a)×(n＋1)／2 ＋ a×n＝(n＋1)(1−a)／2 ＋ na。よってエが正解。存在しない場合に必ず n 回比較する点を na の項で正しく加算している。（出典: 令和5年度 春期 応用情報技術者試験 午前 問6）
一問一答
全400問を繰り返し学習