次の規則に従って配列の要素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です。
この問題は、ハッシュ法で格納場所が衝突したときの再配置の規則をたどれるかを問うています。
格納先が埋まっていれば、規則(2)、規則(3)の順に別の場所を試します。
【格納の流れ】
16は、16 mod 10＝6なので、空いているA[6]に格納されます。
43は、43 mod 10＝3なので、空いているA[3]に格納されます。
73は、73 mod 10＝3ですが、A[3]は43で埋まっています。
規則(2)で(73＋1) mod 10＝4となり、空いているA[4]に格納されます。
24は、24 mod 10＝4ですが、A[4]は73で埋まっています。
規則(2)で(24＋1) mod 10＝5となり、空いているA[5]に格納されます。
85は、85 mod 10＝5ですが、A[5]は24で埋まっています。
規則(2)の(85＋1) mod 10＝6も、16で埋まっています。
規則(3)で(85＋4) mod 10＝9となり、空いているA[9]に格納されます。
【選択肢別解説】
1：× A[3]には43が格納されており、85は入れません。
2：× A[5]は85の本来の格納先ですが、既に24が入っています。
3：× A[6]は規則(2)で試す場所ですが、既に16が入っています。
4：○ 規則(1)と規則(2)の場所が埋まっているので、規則(3)によりA[9]に格納されます。
【ポイント】
格納先が衝突したキーをシノニムといいます。
衝突時に別の空き場所を順に探す方式をオープンアドレス法といい、試す順番を正確にたどることが大切です。