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

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

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

優先度付きキューの実装に一般的に使われる構造はどれですか。

1. A文字列
2. B順序のない単方向連結リスト
3. Cスタック
4. Dヒープ

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

1. An
2. Bn − 1
3. Cn + 1
4. D2n

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

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

二分探索木のあるノードが右部分木をもっています。その通りがけ順での次のノード（後続ノード）はどこにありますか。

1. A右部分木の最も左のノード
2. B常にその右の子
3. C左部分木の最も右のノード
4. D常にその親

キー 50, 30, 70, 20, 40 をこの順に空の二分探索木に挿入します。30 の左の子は何ですか。

1. A40
2. B50
3. C20
4. D70

単方向連結リストをその場で反転させる時間と追加領域のコストはどれですか。

1. A時間 O(n log n)、追加領域 O(1)
2. B時間 O(n)、追加領域 O(n)
3. C時間 O(n)、追加領域 O(1)
4. D時間 O(1)、追加領域 O(1)

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

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