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

ハッシュテーブルはデータをどのような形で格納しますか。

1. Aソート済みリストのみ
2. Bハッシュ関数で位置が決まるキーと値のペア
3. Cキーが順序付けられた木
4. D固定長の文字列

マップ（辞書）は何を格納しますか。

1. A等しいキーの組
2. B大きさの順にソートされた値
3. C挿入順の値だけ
4. D一意なキーをもつキーと値の組

二分木の帰りがけ順（postorder）の走査は、どの順序でノードを訪問しますか。

1. A右部分木、次にノード、次に左部分木
2. B左部分木、次にノード、次に右部分木
3. C左部分木、次に右部分木、次にノード
4. Dノード、次に左部分木、次に右部分木

ある道路網には 100,000 の交差点があり、それぞれが約 4 つの他の交差点とつながっています。最も適した表現はどれですか。

1. A隣接行列
2. B辺の二分ヒープ
3. C隣接リスト
4. D頂点の 1 つのソート済み配列

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

1. A線形探査法（Linear probing）
2. Bダブルハッシュ法（Double hashing）
3. Cチェイン法（Separate chaining）
4. D二次探査法（Quadratic probing）

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

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C1 2 3 4 5
4. D4 5 2 3 1

赤黒木の規則は、n 個のキーをもつ木の高さについてどのような保証を与えますか。

1. A高さは高々 n / 2 である
2. B高さは高々 2 log₂(n + 1) である
3. C高さはちょうど log₂ n である
4. D高さは高々 log₂ n + 1 である

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

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