次の規則に従って配列の要素A[0]，A[1]，…，A[9]に正の整数kを格納する。
kとして16，43，73，24，85を順に格納したとき，85が格納される場所はどこか。
ここで，x mod yはxをyで割った剰余を返す。
また，配列の要素は全て0に初期化されている。
〔規則〕
(1) A[k mod 10]＝0ならば，k→A[k mod 10] とする。
(2) (1)で格納できないとき，A[(k+1) mod 10]＝0ならば，k→A[(k+1) mod 10] とする。
(3) (2)で格納できないとき，A[(k+4) mod 10]＝0ならば，k→A[(k+4) mod 10] とする。
正答4
解説
正解は4です。
ハッシュ法で、格納場所が衝突したときに別の場所を順に試す規則の問題です。
一つの値について、k mod 10、(k+1) mod 10、(k+4) mod 10の順に空きを調べます。
【計算】
16は16 mod 10＝6なので、A[6]に格納します。
43は43 mod 10＝3なので、A[3]に格納します。
73は73 mod 10＝3ですが、A[3]は使用中です。
そこで(73+1) mod 10＝4のA[4]に格納します。
24は24 mod 10＝4ですが、A[4]は使用中です。
そこで(24+1) mod 10＝5のA[5]に格納します。
85は85 mod 10＝5ですが、A[5]は使用中です。
次の(85+1) mod 10＝6のA[6]も使用中です。
最後の(85+4) mod 10＝9のA[9]は空いているので、85はA[9]に格納されます。
【選択肢別解説】
1：× A[3]には43が格納されています。
85の格納候補はA[5]、A[6]、A[9]であり、A[3]は候補にもなりません。
2：× A[5]は85の最初の候補ですが、すでに24が格納されているため使えません。
3：× A[6]は85の2番目の候補ですが、最初に16が格納されているため使えません。
4：○ 最初の2つの候補が埋まっているため、3番目の候補であるA[9]に格納されます。
【ポイント】
衝突したときに配列内の別の空き場所を探す方式を、オープンアドレス法といいます。
先に格納した値が後の値の格納先を変えるので、必ず格納順に表を埋めていきます。