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

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

 探索方法とその実行時間のオーダの正しい組合せはどれか。ここで,探索するデータ数を 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

【平成17年秋 問11】

【平成16年春 問11】


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