修了試験 2021-01-24実施分 基本情報技術者試験 問9
次の規則に従って配列の要素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]が空いているのでA[6]に格納します。 43は、43 mod 10＝3で、A[3]が空いているのでA[3]に格納します。 73は、73 mod 10＝3ですが、A[3]は使用済みです。 次に74 mod 10＝4を調べ、A[4]が空いているのでA[4]に格納します。 24は、24 mod 10＝4ですが、A[4]は使用済みです。 次に25 mod 10＝5を調べ、A[5]が空いているのでA[5]に格納します。 85は、85 mod 10＝5ですが、A[5]は使用済みです。 次に86 mod 10＝6を調べますが、A[6]も使用済みです。 最後に89 mod 10＝9を調べ、A[9]が空いているのでA[9]に格納します。 【選択肢別解説】 1：× A[3]には43が格納済みで、85の探索候補にも入っていません。 2：× A[5]は85の最初の候補ですが、すでに24が格納されています。 3：× A[6]は85の2番目の候補ですが、すでに16が格納されています。 4：○ 3番目の候補A[(85＋4) mod 10]＝A[9]が空いているので、85はA[9]に格納されます。 【ポイント】 衝突処理の問題は、1つずつ格納するたびに配列の状態を更新して追うことが大切です。 前のデータが後ろにずれて格納されると、後続のデータの衝突が連鎖的に増える点に注意します。まとめて解く
修了試験 2021-01-24実施分を通しで解く（80問）→