修了試験 2019-06-09実施分 基本情報技術者試験 問6
次の規則に従って配列の要素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＋1、k＋4の順に別の場所を探します。 【計算】 16は、16 mod 10＝6で、A[6]が空いているのでA[6]に格納します。 43は、43 mod 10＝3で、A[3]が空いているのでA[3]に格納します。 73は、73 mod 10＝3ですが、A[3]は43で埋まっています。 そこで(73＋1) mod 10＝4を調べ、A[4]が空いているのでA[4]に格納します。 24は、24 mod 10＝4ですが、A[4]は73で埋まっています。 そこで(24＋1) mod 10＝5を調べ、A[5]が空いているのでA[5]に格納します。 85は、85 mod 10＝5ですが、A[5]は24で埋まっています。 (85＋1) mod 10＝6を調べますが、A[6]は16で埋まっています。 (85＋4) mod 10＝9を調べ、A[9]が空いているのでA[9]に格納します。 【選択肢別解説】 1：× A[3]は43が最初に格納された場所です。 85の候補になるのはA[5]、A[6]、A[9]だけです。 2：× A[5]は85の最初の格納先ですが、すでに24が格納されているので使えません。 3：× A[6]は規則(2)で調べる場所ですが、16が格納されているので使えません。 4：○ 規則(3)で調べるA[9]が空いているため、85はA[9]に格納されます。 【ポイント】 ハッシュ法で格納先が重なることを衝突（シノニム）といいます。 この問題のように、別の格納先を決まった規則で探す方法をオープンアドレス法といいます。まとめて解く
修了試験 2019-06-09実施分を通しで解く（80問）→