問題プレビューID: 16ab4333応用情報技術者試験 2014年(平成26年度)春期 午前

問 6
応用情報技術者試験 2014年(平成26年度)春期 午前

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

解説

正解は「エ」です。

線形探索法では,表の先頭から順に比較します。

  • 探索する従業員番号が表に存在する場合(確率 1−a)は,先頭から順に探すときの平均比較回数が (n+1)/2 回になります。
  • 存在しない場合(確率 a)は,最後まで調べて見つからないことが分かるので,n 回の比較が必要になります。

したがって,平均比較回数は (1−a)×(n+1)/2 + a×n となり,エ が正解です。

関連問題

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