解答つきデータ構造ワークシート

ハッシュテーブルにおいて、衝突（collision）とは何ですか。

1. Aキーをまったくハッシュできないこと
2. B2 つの異なるキーが同じインデックスに対応すること
3. C2 つの等しいキーが 2 回格納されること
4. Dテーブルのメモリが不足すること

最大ヒープ性（max-heap property）とは何ですか。

1. Aすべての親のキーがその子のキー以上である
2. Bすべての左の子のキーが右の兄弟のキー以上である
3. Cキーが左から右へソートされている
4. Dすべての葉が最大のキーをもつ

配列では遅いが、連結リストの先頭では速い操作はどれですか。

1. A先頭への挿入
2. B5 番目の要素へのアクセス
3. C固定長配列の長さの取得
4. Dインデックスによる最後の要素の読み取り

ある二分木の根は 1 で、左の子が 2、右の子が 3 です。ノード 2 の子は 4（左）と 5（右）です。行きがけ順の走査はどれですか。

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D1 2 3 4 5

サイズ 7 のハッシュテーブルが h(k) = k mod 7 と線形探査法を使っています。10 を挿入した後、17 はどこに格納されますか。

1. Aインデックス 6
2. Bインデックス 4
3. Cインデックス 3
4. Dインデックス 0

オープンアドレス法を使うハッシュテーブルで、負荷率の最大値はいくつですか。

1. A最大値はない
2. B2
3. C1
4. D0.5

オープンアドレス法を使うハッシュテーブルで、削除に「墓標」（tombstone）マーカーがよく使われるのはなぜですか。

1. Aテーブルがソートされた状態になるから
2. Bスロットを空にすると、他のキーの探査列が途切れる可能性があるから
3. C安全のため削除したキーを永久に保持する必要があり、スロットを再利用できないから
4. D墓標がハッシュ計算を高速化するから

ブルームフィルタは「この要素は集合に含まれるか」という問いにどのように答えますか。

1. A偽陽性はあり得るが、偽陰性はない
2. B数値に対してのみ答えられる
3. C常に正確な答えを返す
4. D偽陰性はあり得るが、偽陽性はない