従業員番号と氏名の対がn 件格納されている表に線形探索法を用いて、与えられた従業員番号から氏名を検索する。 この処理における平均比較回数を求める式はどれか。 ここで、検索する従業員番号はランダムに出現し、探索は常に表の先頭から行う。 また、与えられた従業員番号がこの表に存在しない確率をa とする。
答え エ
【解説】 検索する従業員番号が表に存在する場合、線形探索法を用いると比較回数は (n +1)/2 …(1) になる。 また、存在しない場合の比較回数は n …(1) である。 ここで、検索する従業員番号が表に存在しない確率がa であり、存在する確率が(1-a )であるから、平均比較回数は (エ)になる。
【キーワード】 ・線形探索法
戻る 一覧へ 次へ