トップ過去問一覧応用情報技術者 平成20年・秋 > 問12
問12

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

○正解
×不正解

解説

検索する従業員番号が表に存在する場合、平均比較回数は、(n+1)/2 です。また、存在しない場合の比較回数は、nです。ここで、検索する従業員番号が表に存在しない確率がaであり、存在する確率が(1-a)であることから、平均比較回数は、(n+1)(1-a)/2 + naで求められます。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。