「AP過去問 令和6年度秋期 午前 問6」の版間の差分
(ページの作成:「|AP過去問 令和6年度秋期 午前 問題に戻る AP過去問 令和6年度秋期 午前 問5へ AP過去問 令和6年度秋期 午前 問7へ =='''問6(問題文)'''== =='''回答・解説'''== AP過去問 令和6年度秋期 午前 問5へ AP過去問 令和6年度秋期 午前 問7へ AP過去問 令和6年度秋期 午前#問題||AP過去問 令和6年度秋期 午前…」) |
編集の要約なし |
||
| 6行目: | 6行目: | ||
=='''問6(問題文)'''== | =='''問6(問題文)'''== | ||
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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の倍数 | |||
=='''回答・解説'''== | =='''回答・解説'''== | ||
例えば、a=24、b=10で、nが7のときは、b÷nやa÷nの余りはいずれも3で衝突する。このとき、アの関係にあるか確かめると、a+bは34で7の倍数にはなっていないので誤り、イの関係にあるか確かめると、24-10で、14になる7の倍数になるので、成り立っている。ウの関係について確かめると、7は34の倍数ではないので誤り、エは7は14の倍数ではないので誤りとなる。したがってイが正しい。 | |||
ハッシュの大きさが7の場合、あまり4となる11に対しても、7の倍数の差があるといずれも同じ値で衝突する、11+7=18で、18÷7は2余り4となる。18+7の25も25÷7は3あまり4となる。同じあまりになるもの同士の関係はつねに差が7の倍数になる。したがって、 | |||
<span style = "background:linear-gradient(transparent 75%, #7fbfff 75%); font-weight:bold; "> | |||
イ a-bがnの倍数</span> | |||
が答えです。 | |||
2024年11月26日 (火) 18:05時点における最新版
問6(問題文)
自然数をキーとするデータを、ハッシュ表を用いて管理する。キー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の倍数
回答・解説
例えば、a=24、b=10で、nが7のときは、b÷nやa÷nの余りはいずれも3で衝突する。このとき、アの関係にあるか確かめると、a+bは34で7の倍数にはなっていないので誤り、イの関係にあるか確かめると、24-10で、14になる7の倍数になるので、成り立っている。ウの関係について確かめると、7は34の倍数ではないので誤り、エは7は14の倍数ではないので誤りとなる。したがってイが正しい。
ハッシュの大きさが7の場合、あまり4となる11に対しても、7の倍数の差があるといずれも同じ値で衝突する、11+7=18で、18÷7は2余り4となる。18+7の25も25÷7は3あまり4となる。同じあまりになるもの同士の関係はつねに差が7の倍数になる。したがって、
イ a-bがnの倍数
が答えです。