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

二分木を定義するものは何ですか。

1. A木がちょうど 2 つのレベルをもつ
2. Bすべてのノードが 2 進数を格納する
3. Cすべてのノードが高々 2 つの子をもつ
4. Dすべてのノードがちょうど 2 つの子をもつ

静的配列と動的配列の主な違いは何ですか。

1. A静的配列はインデックスによるアクセスが遅い
2. B静的配列は数値しか格納できない
3. C動的配列は要素を連結されたノードに格納するので、1 つずつ拡張できる
4. D動的配列は、より大きなメモリブロックに移ることで拡張できる

スタックの一番上に要素を追加する操作の名前は何ですか。

1. Aプッシュ（Push）
2. Bピーク（Peek）
3. Cエンキュー（Enqueue）
4. Dポップ（Pop）

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

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

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

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

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

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

すべての B 木を完全に平衡に保っている性質はどれですか。

1. Aすべての葉が同じ深さにある
2. Bキーは根にだけ格納される
3. Cすべてのノードがちょうど 2 つの子をもつ
4. D各ノードは 1 つのキーを格納する

ソート済み連結リストと比べたスキップリストの主な利点は何ですか。

1. Aキーを順序なしで格納する
2. Bすべてのノードが他のすべてのノードへのポインタを持つので、O(1) の探索が保証される
3. C追加のメモリを使わない
4. D複数レベルの前方ポインタにより期待値 O(log n) で探索できる