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

木のレベル順（level-order）走査を行うのに使われるデータ構造はどれですか。

1. Aスタック
2. Bハッシュテーブル
3. Cキュー
4. D優先度付きキュー

配列では O(1) だが、単方向連結リストでは O(n) となる操作はどれですか。

1. A先頭への挿入
2. Bインデックス i の要素へのアクセス
3. C最初の要素の読み取り
4. D先頭の要素の削除

単方向連結リストでは、各ノードに何が含まれていますか。

1. Aデータと次のノードへの参照
2. Bデータと他のすべてのノードへの参照
3. Cデータのみ
4. Dデータとインデックス

二分最小ヒープの extract-min はどのように動作しますか。

1. A配列の最後の要素を取り除く
2. B根を取り除き、すべての要素を 1 つ左にずらす
3. Cすべての葉から新しい最小値を探す
4. D最後の要素を根に移し、下へ移動させる（sift down）

実行中のプログラムが、有効な関数呼び出しとそのローカル変数を管理するために使うデータ構造はどれですか。

1. Aヒープメモリのキュー
2. Bフレームの二分探索木
3. Cコールスタック
4. D関数のハッシュテーブル

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

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

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

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

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

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