従業員番号と氏名の対がn件格納されている表に線形探索法を用いて,与えられた従業員番号から氏名を検索する。この処理における平均比較回数を求める式はどれか。ここで検索する従業員番号はランダムに出現し,探索は常に表の先頭から行う。また,与えられた従業員番号がこの表に存在しない確率をaとする。
- (n+1)na/2
- (n+1)(1-a)/2
- (n+1)(1-a)/2 + n/2
- (n+1)(1-a)/2 + na
解答
エ
解説
ー
- (n+1)na/2
ー - (n+1)(1-a)/2
ー - (n+1)(1-a)/2 + n/2
ー - (n+1)(1-a)/2 + na
ー
参考情報
分野・分類
分野 | テクノロジ系 |
大分類 | 基礎理論 |
中分類 | アルゴリズムとプログラミング |
小分類 | アルゴリズム |
出題歴
- AP 令和5年度春期 問6
- AP 平成26年度春期 問6