読者です 読者をやめる 読者になる 読者になる

技術士の技事録

情報工学部門の技術士が、IT技術動向、資格対策等を、勝手気ままに語ります。

技術士第一次試験専門科目 平成24年度 Ⅲ-11

問題

キーとデータのマッピングを実現するための二分探索木とハッシュデータ構造に関する次の説明のうち,最も適切なものはどれか。なお,キーとデータの組の個数をηとし,キーとデータのバイト数は一定であるとする。

選択肢

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

 

答え

 ⑤

解説

 

次の問題へ専門科目TOPへ技術士TOPへ