問題プレビューID: 7ea53592応用情報技術者試験 2023年(令和5年度)春期 午前

問 6
応用情報技術者試験 2023年(令和5年度)春期 午前

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

解説

正解は「エ」です。

線形探索では,表の先頭から順に比較します。表に存在する場合(確率 1−a1-a),見つかる位置は先頭から 1,2,…,nn 番目のいずれかで,平均比較回数は 1+2+⋯+nn=n+12\dfrac{1+2+\cdots+n}{n} = \dfrac{n+1}{2} です。表に存在しない場合(確率 aa),最後まで比較して見つからないので,比較回数は nn です。したがって平均比較回数は,それぞれに確率を掛けて加えた

(n+1) (1−a)2+na\dfrac{(n+1)\,(1-a)}{2} + na

となります。

  • ア・イ・ウ: 存在する場合の平均比較回数 n+12\dfrac{n+1}{2} と,存在しない場合の比較回数 nn に,それぞれの確率を正しく掛け合わせていません。

関連問題

本文が同じ・似ている問題を表示しています