平成24年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−11
キーとデータのマッピングを実現するための二分探索木とハッシュデータ構造に関する
次の説明のうち、最も適切なものはどれか。なお、キーとデータの組の個数を とし、
キーとデータのバイト数は一定であるとする。

 @ コリジョンを無視できる状況でハッシュ表を用いた場合、キーとデータの追加に
   必要な時間計算量は O(logn) より小さくできない。
 A 二分探索木に新しいキーとデータを追加する場合の時間計算量は、
   最悪でも O(logn) である。
 B 二分探索木を実現するときの領域計算量は O(logn) である。
 C ハッシュ表に登録されているキーを昇順に取り出すための時間計算量は
   O(logn) である。
 D ハッシュ表でコリジョンを開アドレス法 (open addressing) で処理している場合、
   キーの個数が大きくなったときに表を拡張するために要する時間計算量は
   O(n) である。



【正解】 D
@1回の計算で一意データが決まるため計算量はO(1)である。
A平均の計算量は O(logn) であり、最悪の計算量は O(n) である。
B領域計算量は O(n) である。
Cランダムに登録されているため、昇順に取り出すためにはソートが必要で、
 O(n2) である。
D正しい。
開アドレス法 (オープンアドレス法) は、コリジョン (衝突) が発生した場合に、
 再ハッシュ (リハッシュ) を行い、ハッシュ表とは別の領域にデータを登録する方法
 である。


EXCELのマクロのご相談なら ファーストマクロ 



W−10 目次 W−12
ファーストマクロ TOPページ