「資格試験/情報処理技術者試験/高度共通午前１/過去問2013年秋午前１/問２回答」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* 正解 イ [[次の問題へ>資格試験/情報処理技術者試験/高度共通午前１/過去問2013年秋午前１/問３]]
#include(資格試験/情報処理技術者試験/高度共通午前１/過去問2013年秋午前１/問２)
* 解説
余りを求める関数による、ハッシュの衝突の問題です。
「自然数をキーとするデータをハッシュ表を用いて管理する」とはどのようなものでしょうか。
** 自然数をキーとするデータ
自然数をキーとするデータとは、以下の様な物だと思ってください。
キーとデータの組み合わせで、JavaScriptの連想配列やJavaのHashMapにデータを
|キー|データ|
|1|りんご|
|7|プリン|
|10|ドーナツ|
|3|チョコレート|
** ハッシュ表を用いて管理
例えば問題文の、ハッシュ表の大きさ n が７だとしたら以下の様なハッシュ表が出来上がります。
|ハッシュ値|データ|
|0|プリン|
|1|りんご|
|2||
|3|チョコレート&br()ドーナツ|
|4||
|5||
|6||
データが少なくて申し訳ありませんが、ハッシュ表の3番にチョコレートとドーナツが入っています。この状態が問題文の「キーａとキーｂが衝突する」に相当します。
さてさて、それでは本題の「キーａとキーｂが衝突する条件」について考えてみましょう。
上の例では、チョコレートのキー「3」とドーナツのキー「10」がキーａとキーｂに当たります。
ハッシュ表の大きさｎは「7」ですね。
これで各選択肢に数字を当てはめてみると以下のようになります。
>ア 3 + 10 が 7 の倍数 ・・・ 13 は 7 の倍数ではないので不正解
>イ 3 - 10 が 7 の倍数 ・・・ -7 は 7 の倍数なので正解
>ウ 7 が 3 + 10 の倍数 ・・・ 7 は 13 の倍数ではないので不正解
>エ 7 が 3 - 10 の倍数 ・・・ 7 は -7 の倍数なので正解
イとエの式が成立したので、もう少し検証してみましょう。次はキーａを「3」、キーｂを「17」としてみます。
>イ 3 - 17 が 7 の倍数 ・・・ -14 は 7 の倍数なので正解
>エ 7 が 3 - 17 の倍数 ・・・ 7 は -14 の倍数ではないので不正解
というわけで、正解はイです。
[[前の問題へ>資格試験/情報処理技術者試験/高度共通午前１/過去問2013年秋午前１/問１]] [[次の問題へ>資格試験/情報処理技術者試験/高度共通午前１/過去問2013年秋午前１/問３]]
