アルゴリズムとプログラミング
平成23年度 秋期 基本情報技術者試験 午前 問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]
出典:平成23年度 秋期 基本情報技術者試験 午前 問6
答えと解説を見る
正解:エ
覚える知識
オープンアドレス法によるハッシュ衝突時の格納位置のトレース
ハッシュ衝突時に別の空き位置を順に探して格納する方式がオープンアドレス法である。
この問題で必要なこと
各kを順に格納し、衝突時は+1、+4の位置を試す規則に従って85の格納位置A[9]を求める。
ひっかけ
衝突時の再試行規則の順序を誤ったり、既に埋まった位置を空きとみなすと別の添字を選ぶ。
この知識の出題:本試験系 3 回・免除試験 7 回(公開問題での観測値)