うごく基本情報

令和5年度 公開問題 科目B 問4

ハッシュ法 ・ 大域変数 ・ トレース

次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 add は,引数で指定された正の整数 value を大域の整数型の配列 hashArray に格納する。格納できた場合は true を返し,格納できなかった場合は false を返す。
ここで,整数 value を hashArray のどの要素に格納すべきかを,関数 calcHash1 及びcalcHash2 を利用して決める。
手続 test は,関数 add を呼び出して,hashArray に正の整数を格納する。手続test の処理が終了した直後の hashArray の内容は,[ ]である。

大域: 整数型の配列: hashArray

○論理型: add(整数型: value)
  整数型: i ← calcHash1(value)
  if (hashArray[i] = -1)
    hashArray[i] ← value
    return true
  else
    i ← calcHash2(value)
    if (hashArray[i] = -1)
      hashArray[i] ← value
      return true
    endif
  endif
  return false

○整数型: calcHash1(整数型: value)
  return (value mod hashArrayの要素数) + 1

○整数型: calcHash2(整数型: value)
  return ((value + 3) mod hashArrayの要素数) + 1

○test()
  hashArray ← {5個の -1}
  add(3)
  add(18)
  add(11)
答え
ア[-1,3,-1,18,11]
イ[-1,11,-1,3,-1]
ウ[-1,11,-1,18,-1]
エ[-1,18,-1,3,11]
オ[-1,18,11,3,-1]

出典:令和5年度 基本情報技術者試験 科目B 公開問題 問4

正解と解説を見る

正解:エ

ポイント:ハッシュ表:まず1つ目の関数で位置を決め、埋まっていたら2つ目の関数の位置に入れる。位置は「mod 要素数」+1。

hashArray は要素数5で、全部 -1(空き)から始めます。
add(3):calcHash1 = (3 mod 5)+1 = 4。hashArray[4] は空きなので 3 を入れる。→ {-1, -1, -1, 3, -1}
add(18):calcHash1 = (18 mod 5)+1 = 4。hashArray[4] は 3 で埋まっている。calcHash2 = ((18+3) mod 5)+1 = 2。空きなので 18 を入れる。→ {-1, 18, -1, 3, -1}
add(11):calcHash1 = (11 mod 5)+1 = 2。hashArray[2] は 18 で埋まっている。calcHash2 = ((11+3) mod 5)+1 = 5。空きなので 11 を入れる。→ {-1, 18, -1, 3, 11}
よって(エ)。
よくある間違い:「+1」を忘れて、位置を1つずつ前にずらしてしまう(配列の要素番号は1から始まるので、mod の結果 0〜4 に 1 を足して 1〜5 にしています)。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

サイトで、1行ずつ動かして読む →