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

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

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

静的配列と動的配列の主な違いは何ですか。

1. A動的配列は要素を連結されたノードに格納するので、1 つずつ拡張できる
2. B静的配列は数値しか格納できない
3. C静的配列はインデックスによるアクセスが遅い
4. D動的配列は、より大きなメモリブロックに移ることで拡張できる

木において、兄弟（sibling）ノードとは何ですか。

1. A子をもたないノード
2. B同じ親をもつノード
3. Cあるノードとその親
4. D異なる部分木の同じ深さにあるノード

配列に格納された二分最小ヒープ（インデックスは 0 から）において、インデックス i のノードの子はどこにありますか。

1. A2i + 1 と 2i + 2
2. Bi + 1 と i + 2
3. Ci/2 と i/2 + 1
4. D2i と 2i + 1

AVL 木と赤黒木が保証するものは何ですか。

1. Aキーが挿入順に格納されること
2. Bどの場合でも定数時間での探索
3. C2 つの子を持つノードが存在しないこと
4. D再平衡化による O(log n) の高さ

容量 n の配列に格納された循環キューで、インデックス i の次の位置はどのように計算されますか。

1. A2i + 1
2. Bi + 1
3. C(i + 1) mod n
4. D(i − 1) mod n

ハッシュテーブルが正しく動作するためには、ハッシュと等価性はどの規則に従わなければなりませんか。

1. Aハッシュ値は素数でなければならない
2. B等しいキーは等しいハッシュ値をもたなければならない
3. C異なるキーは異なるハッシュ値をもたなければならない
4. Dハッシュ値が等しければキーも等しい

異なるキーをもつ二分木を常に一意に決定する走査の組はどれですか。

1. A行きがけ順と帰りがけ順
2. Bレベル順だけ
3. C行きがけ順だけ
4. D行きがけ順と通りがけ順