平成25年度 秋期
応用情報技術者試験問題と解答
問7
自然数をキーとするデータを、ハッシュ表を用いて管理する。
キー x のハッシュ関数 h (x)を
 h (x) = x mod n
とすると、キー a と b が衝突する条件はどれか。ここで、
n はハッシュ表の大きさであり、x mod n は x を n で割った
余りを表す。

 ア a + b が n の倍数
 イ a − b が n の倍数
 ウ n が a + b の倍数
 エ n が a − b の倍数



【正解】 イ

ハッシュ関数は、ある入力値から唯一に決まる固定値を生成する
関数のことである。
例えば
 x = 100, n = 13 のとき、ハッシュ値は  9
 x = 101, n = 13 のとき、ハッシュ値は 10
 x = 113, n = 13 のとき、ハッシュ値は  9
となり、101,113のハッシュ値は衝突する。
他にも n = 13 のとき、ハッシュ値が 9 になるのは、
9, 22, 35, 48, 61, 74, 87, 100, 113, 126, ・・・
共通するのは 
差が 13 の倍数ということ。
つまり、イの場合になる。

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



問6 目次 問8
ファーストマクロ TOPページ