問6応用情報技術者 令和6年度 秋期
6 / 80問令和6年度 秋期2024年
自然数をキーとするデータを，ハッシュ表を用いて管理する。キーxのハッシュ関数h(x)をh(x) = x mod nとすると，任意のキーaとbが衝突する条件はどれか。ここで，nはハッシュ表の大きさであり，x mod nはxをnで割った余りを表す。
選択肢をえらぶと、答えと解説が出ます
選択肢をえらぶと、
ここに答えと解説が出ます
ここに答えと解説が出ます
正答 2解説
正解は2。キーaとbが衝突するのは、ハッシュ値が等しい、つまり a mod n ＝ b mod n のとき。aとbをnで割った余りが等しければ、差 a−b は余りが打ち消し合ってnの倍数になる。逆に a−b がnの倍数なら余りは等しい。例えば n＝5、a＝13、b＝3 では、どちらも余りは3で、a−b＝10 は5の倍数になる。
- 1は、上の例で a+b＝16 は5の倍数でないのに衝突しているので、条件にならない。
- 3は、nがa+bの倍数という関係は、余りが等しいことと結び付かない。
- 4は、倍数の向きが逆。a−b＝10 に対し n＝5 は10の倍数ではないが衝突している。
根拠：剰余（合同式）の標準的な理解
KEY POINT
x mod n のハッシュでは、二つのキーの差がnの倍数のときに同じ値になり衝突する。「基礎理論」の他の問題
- 令和6年度 秋期 問5次の2分探索木から要素12を削除したとき，その位置に別の要素を移動するだけで2分探索木を再構成するには，削除された要素の位置にどの要素を移動すればよいか。
- 令和6年度 秋期 問7次の特徴をもつプログラム言語及び実行環境であって，オープンソースソフトウェアとして提供されているものはどれか。
- 令和6年度 秋期 問4自動車の先進運転支援システムで使用されるセンサーの説明のうち，適切なものはどれか。
- 令和6年度 秋期 問3式A+B×Cの逆ポーランド表記法による表現として，適切なものはどれか。
- 令和6年度 秋期 問2AIにおける教師あり学習での交差検証に関する記述はどれか。
- 令和6年度 秋期 問1M/M/1の待ち行列モデルにおいて，窓口の利用率が25%から40%に増えると，平均待ち時間は何倍になるか。
出典：令和6年度 秋期 応用情報技術者試験 午前 問6（独立行政法人 情報処理推進機構（IPA））
独立行政法人情報処理推進機構（IPA）が公表している過去問題です。IPA の「過去問題の使用について」に基づき、IPA が指定する形で出典を明記して掲載しています（利用の許諾申請は不要）。問題文・選択肢の内容は変えていません。元の問題冊子から文字を起こす都合で、改行・字間の空白は省き、英数字の全角・半角は元とそろえていない箇所があります。図表は IPA が公表した問題冊子のものです。解説は当サイトが独自に作成したもので、IPA とは関係ありません。
独立行政法人情報処理推進機構（IPA）が公表している過去問題です。IPA の「過去問題の使用について」に基づき、IPA が指定する形で出典を明記して掲載しています（利用の許諾申請は不要）。問題文・選択肢の内容は変えていません。元の問題冊子から文字を起こす都合で、改行・字間の空白は省き、英数字の全角・半角は元とそろえていない箇所があります。図表は IPA が公表した問題冊子のものです。解説は当サイトが独自に作成したもので、IPA とは関係ありません。