アルゴリズムとプログラミング
平成25年度 秋期 基本情報技術者試験 午前 問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]
出典：平成25年度 秋期 基本情報技術者試験 午前 問7
答えと解説を見る
正解：エ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
ハッシュ衝突時は、あらかじめ決めた規則で次の候補位置を順に探して空きに格納する。
この問題で必要なこと
規則(1)〜(3)を順に適用して格納位置をトレースする。16→A[6]、43→A[3]、73→A[4]、24→A[5]、85はA[5]とA[6]が埋まっておりA[9]に格納される。
ひっかけ
途中の衝突の連鎖(73→A[4]、24→A[5])の追跡を誤ると別の位置になる。
この知識の出題：本試験系 3 回・免除試験 7 回（公開問題での観測値）