2016年08月07日

平成28年度 技術士第二次試験問題 情報工学部門 T−12

T−12
自然数をキーとするデータをハッシュ表を用いて管理する。 キー x のハッシュ値を
求めるハッシュ関数を h(x) = x mod n とした場合、キー a と b のハッシュ値が
常に衝突する条件はどれか。 ここで n はハッシュ表の大きさであり、
x mod n は x を n で割った余りを示す。

 @ a + b が n の倍数
 A b − a が n の倍数
 B a ÷ b が n の倍数
 C n が a + b の倍数
 D n が b − a の倍数


【正解】 A
ハッシュ関数は、ある入力値から唯一に決まる固定値を生成する関数のこと。
固定値から入力値を求めることはできない。
例えば
 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 ということ。
つまり、Aの場合になる。


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



タグ:ハッシュ
posted by ファーストマクロ at 00:04| Comment(0) | H28技術士二次試験(情報工学)
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント: