平成16年春期試験午前問題 問13

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
16進数で表される9個のデータ1A,35,3B,54,8E,A1,AF,B2,B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数f(データ)=mod(データ,8)で求めたとき,最初に衝突が起こる(既に表にあるデータと等しいハッシュ値になる)のはどのデータか。ここで,mod(a,b)はaをbで割った余りを表す。

  • 54
  • A1
  • B2
  • B3
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
9個のデータを10進数で表記すると、26,53,59,84,142,161,175,178,179になります。
13_1.gif
それぞれについて関数 f(データ)=mod(データ,8)を用いてハッシュを求めると、2,5,3,4,6,1,7,2,3となり、データが「26」と「178」の間で最初の衝突が起こることがわかります。
13_2.gif
10進数178は、16進数状態のデータでB2だったので、これが正解となります。

【別解】
16進数の2桁目は「16×n」なので必ず8で割り切れます。これを利用して2桁目を無視すれば素早く計算できます。
13_3.gif

この問題の出題歴


Pagetop