アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20180128 実施分 問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] に格納する。
- ア A[3]
- イ A[5]
- ウ A[6]
- エ A[9]
出典：基本情報技術者試験 科目A免除 修了試験 20180128 実施分 問6
答えと解説を見る
正解：エ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
オープンアドレス法は、衝突時に別の空き位置を所定の規則で探して格納する方式。
この問題で必要なこと
16→A[6]、43→A[3]、73は衝突してA[4]、24は衝突してA[5]。85は余り5で衝突し、(85+1)mod10=6も埋まっているため、(85+4)mod10=9のA[9]に入る。
ひっかけ
衝突時の再探索規則を適用する順序を誤ると別の添字になる。
この知識の出題：本試験系 3 回・免除試験 7 回（公開問題での観測値）