ITの基礎知識｜ITパスポート・基本情報

基本情報技術者平成20年春問14

2017.10.05

キーｘのハッシュ関数として h(x)＝mod（x，97）を用いるとき，キー 1094 とハッシュ値が一致するものは，キー１～1000 の中に幾つあるか。ことで，mod（x，97)は x を 97 で割った余りを表す。

ア：　　9
イ：　　10
ウ：　　11
エ：　　12

基本情報過去問 , アルゴリズム

前の記事へ次の記事へ

正解：　ウ

解説：

1094 のハッシュ値を計算する。

1094÷97＝11　余り27 　よって、ハッシュ値は 27 である。

１～1000 の中に 97 で割った余りが 27 になるものを数える。

ハッシュ値が 27 になる最小値は、97×０＋27＝27 である。また、 1000÷97＝10.3… なので、97×10＋27＝997 となり、ハッシュ値が 27 の最大値である。

よって、商が０から 10 までの 11 個となる。