問題プレビューID: 5367ba0b基本情報技術者試験 午前免除試験 2019年12月8日

問 9
基本情報技術者試験 午前免除試験 2019年12月8日

キーが小文字のアルファベット 1 文字(a,b,…,z のいずれか)であるデータを,大きさが 10 のハッシュ表に格納する。ハッシュ関数として,アルファベットの ASCII コードを 10 進記法で表したときの 1 の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCII コードでは,昇順に連続した 2 進数が,アルファベット順にコードとして割り当てられている。

解説

正解は「エ」です。

ハッシュ値は ASCII コードの 1 の位なので,文字の ASCII コードを 10 で割った余りを求めます。アルファベットには昇順に連続したコードが割り当てられているため,a のコードを nn とすると,各文字のコードは a から順に n,n+1,…,n+25n, n+1, \ldots, n+25 となります。

  • ア: a(nn)と i(n+8n+8)は 8 離れており,1 の位は一致しません。
  • イ: b(n+1n+1)と r(n+17n+17)は 16 離れており,1 の位は一致しません。
  • ウ: c(n+2n+2)と l(n+11n+11)は 9 離れており,1 の位は一致しません。
  • エ: d(n+3n+3)と x(n+23n+23)は 20 離れています。20 は 10 の倍数なので 1 の位が一致し,衝突します。

実際に ASCII コードで確認すると,d は 100,x は 120 で,いずれも 1 の位は 0 です。したがって,正解は「エ」です。

関連問題

本文が同じ・似ている問題を表示しています