修了試験 2015-07-26実施分 基本情報技術者試験 問6

解説

正解は3です。 表探索の方式の一つであるハッシュ法の特徴を問う問題です。 ハッシュ法は、キーの値をハッシュ関数で計算し、その結果を格納場所（アドレス）として使う方式です。 【選択肢別解説】 1：× 2分木を用いるのは2分探索木による探索です。 ハッシュ法は木構造をたどらず、計算で格納場所を直接求めます。 2：× ハッシュ法では、異なるキーから同じ格納場所が計算される衝突（シノニム）が起こり得ます。 そのため、衝突時に別の場所へ格納する処理などが必要になります。 3：○ キーをハッシュ関数に入れて得た関数値によって格納場所を決めます。 探索時も同じ計算をすれば、格納場所に直接たどり着けます。 4：× 探索時間が表全体の大きさにほぼ比例するのは、先頭から順に調べる線形探索です。 ハッシュ法は衝突が少なければ、表の大きさにほとんど関係なく一定の時間で探索できます。 【ポイント】 線形探索は表の大きさに比例し、2分探索は表の大きさの対数に比例します。 ハッシュ法は衝突が少ない限りほぼ一定の時間で探索でき、その代わり衝突への対策が必要です。