自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571, 1168, 1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ、全てのハッシュ値が衝突した。このとき使用した除数は幾つか。
選択肢
- ア193
- イ197
- ウ199
- エ211
正解と解説
正解：ウ 199
三つのキー値が同じ除数nで同じ剰余になるということは、それらの差がすべてnの倍数になるということである。差を取ると1168-571＝597、1566-1168＝398、1566-571＝995となる。597＝3×199、398＝2×199、995＝5×199なので、最大公約数は199であり、これが使用した除数である。
選択肢ごとの解説
- ア193では571÷193の余りは185、1168÷193の余りは10となり一致しない。
- イ197でも571の余りは177、1168の余りは183で衝突しない。
- ウ正しい。571＝199×2+173、1168＝199×5+173、1566＝199×7+173となり、いずれも余りは173で一致する。
- エ211では571の余りは149、1168の余りは112となり一致しない。
この問題に出た用語
同じ分野の他の問題
- 異なるn個のデータが昇順に整列された表がある。この表をm個のデータごとのブロックに分割し、各ブロックの最後尾のデータだけ…2025年度 秋期 問3
- A, B, Cの順序で入力されるデータがある。各データについてスタックへの挿入と取出しを1回ずつ行うことができる場合、デ…2021年度 春期 問2
- 自然数をキーとするデータを、ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)を h(x) = x mod n と…2024年度 秋期 問3
- 各ノードがもつデータを出力する再帰処理f(ノード n)を定義した。この処理を、図の2分木の根(最上位のノード)から始めた…2024年度 春期 問3
- あるデータ列を整列したら状態0から順に状態1、2、・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3…2023年度 秋期 問3
出典・参考
最終更新：2026-10-07／解説・選択肢ごとの解説は資格暗記が独自に作成しています。問題文と選択肢の出典は上記のとおりです。