技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。

�@　コリジョンを無視できる状況でハッシュ表を用いた場合、キーとデータの追加に必要な時間計算量は Ｏ(logn) より小さくできない。

�A　二分探索木に新しいキーとデータを追加する場合の時間計算量は、最悪でも Ｏ(logn) である。

�B　二分探索木を実現するときの領域計算量は Ｏ(logn) である。

�C　ハッシュ表に登録されているキーを昇順に取り出すための時間計算量は Ｏ(n) である。

�D　ハッシュ表でコリジョンを開アドレス法 (open addressing) で処理している場合、キーの個数が大きくなったときに表を拡張するために要する時間計算量はＯ(n)である。

�@　1回の計算で一意データが決まるため計算量は Ｏ(1)である。

�A　平均の計算量は Ｏ(logn) であり、最悪の計算量は Ｏ(n) である。

�B　領域計算量は Ｏ(n) である。

�C　ランダムに登録されているため、昇順に取り出すためにはソートが必要で、Ｏ(n²) である。

�D　正しい。開アドレス法 (オープンアドレス法) は、コリジョン (衝突) が発生した場合に、再ハッシュ (リハッシュ) を行い、ハッシュ表とは別の領域にデータを登録する方法である。