アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20151220 実施分 問7
次の規則に従って配列の要素 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免除 修了試験 20151220 実施分 問7
答えと解説を見る
正解：エ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
オープンアドレス法は衝突時に別の規則で次の空き位置を探す。
この問題で必要なこと
16→A6、43→A3、73→A3衝突でA4、24→A4衝突でA5、85→A5,A6が埋まっておりA9。
ひっかけ
k+1 のあとに k+4 を試す手順を飛ばして誤った位置を選ばせる。
この知識の出題：本試験系 3 回・免除試験 7 回（公開問題での観測値）