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

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

1. A左部分木、次に右部分木、次にノード
2. Bノード、次に左部分木、次に右部分木
3. C左部分木、次にノード、次に右部分木
4. D上から 1 レベルずつ

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

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

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

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

高さを辺の数で数えるとき、高さ h の完全（perfect）二分木にはいくつのノードがありますか。

1. A2^h
2. Bh²
3. C2^h+1 − 1
4. D2h + 1

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

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

二分探索木で最小のキーはどのように見つけますか。

1. A根だけを見る
2. Bすべての葉を訪問して比べる
3. C根から左の子がなくなるまで左の子をたどる
4. D根から右の子がなくなるまで右の子をたどる

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

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

キー 5, 3, 8, 1 をこの順に、空の配列ベースの二分最小ヒープに挿入します。最終的な配列はどれですか。

1. A[1, 3, 8, 5]
2. B[3, 1, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 5, 8]