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

木の高さは一般にどのように定義されますか。

1. A根の子の数
2. B木の葉の数
3. C根から葉までの最も長い経路上の辺の数
4. D根と葉をすべて含めた、木に含まれるノードの総数

単方向連結リストでは、各ノードに何が含まれていますか。

1. Aデータのみ
2. Bデータと他のすべてのノードへの参照
3. Cデータとインデックス
4. Dデータと次のノードへの参照

n 個のノードをもつ木には何本の辺がありますか。

1. An − 1
2. Bn
3. C2n
4. Dn + 1

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

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

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

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

負荷率がしきい値を超えた後にハッシュテーブルが再ハッシュ（rehash）すると、何が起こりますか。

1. Aより大きなテーブルが確保され、すべてのキーが挿入し直される
2. B既存のキーがその場でソートされる
3. C場所を空けるために最も古いキーが削除される
4. D衝突しているキーだけが、テーブルの末尾にある新しいオーバーフローリストに移される

配列の各要素について、その右側にある次に大きい要素を、合計 O(n) 時間で求めたいとします。役立つ構造はどれですか。

1. Aすべての要素のハッシュテーブル
2. B要素ごとに作り直す二分探索木
3. C要素のすべての組を保持するキュー
4. D答えを待っている要素を保持するスタック

ダブルハッシュ法が主に軽減する線形探査法の問題はどれですか。

1. Aキーの値を読み取る O(n) のコスト
2. Bキーをテーブルに格納する必要があること
3. Cハッシュ関数が必要であること
4. D使用中のスロットが長く連なる一次クラスタリング