修了試験 2018-01-28実施分 基本情報技術者試験 問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 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]は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]は空いているので、85はA[9]に格納されます。 【選択肢別解説】 1：× A[3]は43を格納した場所で、85の候補である5、6、9のどれにも当たりません。 2：× A[5]は85の最初の候補ですが、すでに24が格納されています。 3：× A[6]は規則(2)の候補ですが、すでに16が格納されています。 4：○ 規則(3)の(85＋4) mod 10＝9で、空いているA[9]に格納されます。 【ポイント】 衝突時に別の場所を順に探す方式を、オープンアドレス法といいます。 先に格納した値が後の値の格納先を押し出していくので、格納順どおりに配列の状態を1つずつ更新して追うことが大切です。まとめて解く
修了試験 2018-01-28実施分を通しで解く（80問）→