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

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

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

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

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

テキストエディタの「元に戻す」（undo）機能に最も適したデータ構造はどれですか。

1. Aハッシュセット
2. Bスタック
3. Cグラフ
4. Dキュー

あるアプリケーションには高速な検索が必要で、さらにキーをソート順に一覧にしたり、範囲クエリに答えたりする必要もあります。最も適した構造はどれですか。

1. Aハッシュテーブル
2. Bソートされていない連結リスト
3. Cスタック
4. D平衡二分探索木

インデックス 0 から始まる配列に格納された二分ヒープで、インデックス i のノードの親はどこにありますか。

1. Aインデックス i − 1
2. Bインデックス ⌊i / 2⌋ + 1
3. Cインデックス ⌊(i − 1) / 2⌋
4. Dインデックス 2i + 1

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

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

ランクによる合併（union by rank）も経路圧縮も使わない場合、n 要素の union-find 構造での 1 回の find の最悪コストはどれですか。

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

ハッシュテーブルが正しく動作するためには、ハッシュと等価性はどの規則に従わなければなりませんか。

1. A異なるキーは異なるハッシュ値をもたなければならない
2. Bハッシュ値は素数でなければならない
3. C等しいキーは等しいハッシュ値をもたなければならない
4. Dハッシュ値が等しければキーも等しい