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