問題プレビューID: 37619a8c基本情報技術者試験 2023年(令和5年度)公開問題 科目B

問 4
基本情報技術者試験 2023年(令和5年度)公開問題 科目B

次の記述中の [ ] に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 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)
解説

正解は「エ」です。 二段階のハッシュ計算による格納処理を順にトレースします。配列の要素数は 5 です。

  1. add(3) の実行:
    • calcHash1(3) = (3 mod 5) + 1 = 4
    • hashArray[4] は -1 なので、hashArray[4] ← 3 となり格納成功。
  2. add(18) の実行:
    • calcHash1(18) = (18 mod 5) + 1 = 4
    • hashArray[4] には既に 3 があるため、calcHash2 を実行。
    • calcHash2(18) = ((18 + 3) mod 5) + 1 = (21 mod 5) + 1 = 2
    • hashArray[2] は -1 なので、hashArray[2] ← 18 となり格納成功。
  3. add(11) の実行:
    • calcHash1(11) = (11 mod 5) + 1 = 2
    • hashArray[2] には既に 18 があるため、calcHash2 を実行。
    • calcHash2(11) = ((11 + 3) mod 5) + 1 = (14 mod 5) + 1 = 5
    • hashArray[5] は -1 なので、hashArray[5] ← 11 となり格納成功。

結果、hashArray の内容は {-1, 18, -1, 3, 11} となります。

関連問題

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