アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20190609 実施分 問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免除 修了試験 20190609 実施分 問6（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：エ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
衝突時は規則に従い別の候補位置を順に試して、空きがあれば格納する。
この問題で必要なこと
16→A[6]、43→A[3]、73→A[3]埋まり→A[4]、24→A[4]埋まり→A[5]、85→A[5]埋まり→A[6]埋まり→A[(85+4) mod 10]=A[9]。
ひっかけ
途中の衝突回数や順序を誤り、A[5]やA[6]に入れてしまう誤り。
この知識の出題：本試験系 3 回・免除試験 7 回（公開問題での観測値）