基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [平成31年春午前] [平成31年春午後]

平成24年 秋期 基本情報技術者 午前 問03
問03   探索方法と実行時間

 探索方法とその実行時間のオーダの正しい組合せはどれか。ここで,探索するデータの数を n とし, ハッシュ値が衝突する(同じ値になる)確率は無視できるほど小さいものとする。 また,実行時間のオーダが n2 であるとは,n 個のデータを処理する時間が cn2( c は定数)で抑えられることをいう。

      2分探索     線形探索      ハッシュ探索  
  ア    log2 n      n      1
  イ   n log2 n      n     log2 n
  ウ   n log2 n     n2     1
  エ    n2      1      n

解答←クリックすると正解が表示されます

解説

探索方法の実行時間

 2分探索とはバイナリサーチとも言われ、線形探索よりデータを探索し易い。
実行時間のオーダ=logn
線形探索とはデータを上から比較し、目的のデータを探索する
実行時間のオーダ=n

ハッシュ探索とはデータのアドレスを得る
実行時間のオーダ=1

【平成19年秋 問11】
【平成17年秋 問11】
【平成16年春 問11】


[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]