トップ過去問一覧基本情報技術者 平成24年・秋 > 問3
問3

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

○正解
×不正解

解説

 

 

□ 2分探索

あらかじめデータをソートしておくことによって、1回の比較で探索するデータの数を半分に絞ることができます。

データの数を2で何回割れば1になるか、言い換えると、nは2の何乗かを求めればよいので、実行時間のオーダはlog2nになります。

 

□ 線形探索

データを先頭から順番に探索していきます。

従って実行時間のオーダはデータ量に比例し、nとなります。

 

□ ハッシュ探索

探索するデータと対になるキーの値を決め、ハッシュ関数を用いてキーの値からデータの格納アドレス(ハッシュ値)を求めることによってアクセスする方法です。ハッシュ値が同じ値になる確率が無視できるほど小さい場合、データと格納アドレスは1対1の関係になります。

従って、実行時間のオーダはデータ量に関わらず1となります。

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

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