基本情報技術者試験の公開問題を解こう！（令和5年度・科目B）（4）「関数呼び出し（2）」

基本情報技術者試験の令和5年度の公開問題（科目B）を解いてみよう。

〔プログラム〕 
大域: 整数型の配列: 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}

✅ 問題の概要

この問題は「ハッシュ法（オープンアドレス法）」を使った整数格納のシミュレーション問題である。

📌 初期情報（重要ポイント）

• hashArray は「要素数 5」の配列。
• 最初はすべて -1 で初期化されている。

  初期状態: {-1, -1, -1, -1, -1}

• 配列の 要素番号は1から始まる（←ここ大事！）

📘 使用する関数

🔹 calcHash1(value)

(value mod 配列サイズ) + 1

🔹 calcHash2(value)

((value + 3) mod 配列サイズ) + 1

🔹 add(value)

1. calcHash1(value)でインデックスを決める。
2. その場所が空ならそこに格納 → true。
3. すでに使われていたら、calcHash2(value)で再計算して別の場所を試す。
4. それでもダメなら → false

🧪 実際の処理（手続test）

hashArray ← {5個の -1}
add(3)
add(18)
add(11)

▶ add(3)

• calcHash1(3) = (3 mod 5) + 1 = 3 + 1 = 4
• hashArray[4] = -1 → 空なので、格納する。
  → hashArray[4] = 3

{-1, -1, -1, 3, -1}

▶ add(18)

• calcHash1(18) = (18 mod 5) + 1 = 3 + 1 = 4
• hashArray[4] = 3 → すでに埋まってる！

→ 次に calcHash2(18) を試す：

• calcHash2(18) = ((18 + 3) mod 5) + 1 = (21 mod 5) + 1 = 1 + 1 = 2
• hashArray[2] = -1 → 空なので、格納する。
  → hashArray[2] = 18

{-1, 18, -1, 3, -1}

▶ add(11)

• calcHash1(11) = (11 mod 5) + 1 = 1 + 1 = 2
• hashArray[2] = 18 → 埋まってる！

→ 次に calcHash2(11) を試す

• calcHash2(11) = ((11 + 3) mod 5) + 1 = (14 mod 5) + 1 = 4 + 1 = 5
• hashArray[5] = -1 → 空なので、格納する。
  → hashArray[5] = 11

{-1, 18, -1, 3, 11}

🟩 答えの確認

選択肢「エ」が正解となる。

{ -1, 18, -1, 3, 11 }

• ハッシュ関数の計算式は確実に理解しよう！
• 要素番号が1始まりなので要注意！
• 値の格納を手順通りに紙に書き出して追ってみるとよい。