平成18年 秋期 基本情報技術者 午前 問15

次の規則に従って配列の要素A[0], A[1], …, A[9]に正の整数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]


答え エ


解説
16, 43, 73, 24, 85の順にデータを格納し、答えを求めます。
まず、A[0], A[1], …, A[9]は0に初期化されています。

  • 16を格納
    規則の(1)で16 mod 10 = 6でA[6] = 0なので、A[6] = 16になります。
  • 43を格納
    規則の(1)で43 mod 10 = 3でA[3] = 0なので、A[3] = 43 になります。
  • 73を格納
    規則の(1)で73 mod 10 = 3でA[3] = 43 ≠ 0なので、規則の(2)を適用します。
    規則の(2)で(73 + 1) mod 10 = 4でA[4] = 0なので、A[4] = 73になります。
  • 24を格納
    規則の(1)で24 mod 10 = 4でA[4] = 73 ≠ 0なので、規則の(2)を適用します。
    規則の(2)で(24 + 1) mod 10 = 5でA[5] = 0なので、A[5] = 24になります。
  • 85を格納
    規則の(1)で85 mod 10 = 5でA[5] = 24 ≠ 0なので、規則の(2)を適用します。
    規則の(2)で(85 + 1) mod 10 = 6でA[6] = 16 ≠ 0なので、規則の(3)を適用します。
    規則の(3)で(85 + 4) mod 10 = 9でA[9] = 0なので、A[9] = 85(エ)になります。


キーワード
・ハッシュ探索

キーワードの解説
  • ハッシュ探索
    ハッシュ探索ではデータを格納する位置を計算によって求めます。
    その計算式をハッシュ関数と呼びます。(この問題では規則がハッシュ関数になります。)
    ハッシュ探索ではハッシュ関数がわかれば、探したいデータの格納位置が計算で簡単に求められるので、探索する時間が非常に短く高速に処理を求めることができます。
    ただし、ハッシュ値がぶつかったときの処理の考慮が必要になるのが、使用時の注意点です。

もっと、「ハッシュ探索」について調べてみよう。

戻る 一覧へ 次へ