アルゴリズムとプログラミング

平成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 回(公開問題での観測値)

この知識をアプリで解いて覚える レッスン「ハッシュ法と衝突の扱い」で学ぶ

同じ知識の過去問