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

抽象データ型としての集合（set）を定義する特徴は何ですか。

1. A要素をソート順に格納する
2. Bキーと値の組を格納する
3. C一方の端でだけアクセスを許す
4. D重複なしに要素を格納する

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

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

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

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

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

1. Ah²
2. B2^h
3. C2h + 1
4. D2^h+1 − 1

2 つのスタックでキューを実装します。「in」スタックに push し、「out」スタックから pop し、「out」が空になったら「in」から補充します。1 回の操作あたりのならしコストはどれですか。

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(1)

キーをソート済みの順序で挿入した場合、n 個のノードを持つ二分探索木の最悪の高さはいくつですか。

1. A√n
2. Blog₂ n
3. C1
4. Dn（連結リストのようになる）

基数木（radix tree、圧縮トライ）は通常のトライをどのように改良していますか。

1. A子が 1 つだけのノードの連なりを、文字列でラベル付けされた 1 本の辺にまとめる
2. B各単語の最初の文字だけを保持する
3. C各ノードの子を頻度順にソートする
4. D各単語を別々のノードではなく、根にあるハッシュテーブルに格納する

隣接行列として格納された V 頂点のグラフに対する幅優先探索の実行時間はどれですか。

1. AO(V²)
2. BO(V + E)
3. CO(E log V)
4. DO(V)