必ず受かる情報処理技術者試験

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験，基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 応用情報技術者
  3. 平成21年度春季問題一覧
  4. 平成21年度春季問題8-解答・解説-分析

平成21年度春季問題

問題8

相異なるn 個のデータが昇順に整列された表がある。 この表をm 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。 次に、当該ブロック内を線形探索して目的のデータを探し出す。 このときの平均比較回数を表す式はどれか。 ここで、m は十分大きく、n はm の倍数とし、目的のデータは必ず表の中に存在するものとする。

相異なるn 個のデータが昇順に整列された表がある。 この表をm 個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけを線形探索することによって、目的のデータの存在するブロックを探し出す。 次に、当該ブロック内を線形探索して目的のデータを探し出す。 このときの平均比較回数を表す式はどれか。 ここで、m は十分大きく、n はm の倍数とし、目的のデータは必ず表の中に存在するものとする。

解答：イ

＜解説＞

  1. ブロックは全部で、
    n
    m
    個ある。
  2. 線形探索の比較回数は、最小で1回，最大でデータの総和である。したがって、データの総数÷2で目的のデータを見つけることができる。したがって、平均比較回数は、
    n
    2m
    となる。
  3. ブロックの中身の検索を行う。個々のブロックはm個なので、
    n
    2
    となる。
  4. したがって、
    n ＋ n
    2m 2
    となる。