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

配列の要素はメモリにどのように格納されますか。

1. Aメモリページの木の中に
2. B1 つの連続したブロックに、順に並んで
3. Cばらばらに、ポインタでつながれて
4. Dハッシュで選ばれたランダムな位置に

木において、兄弟（sibling）ノードとは何ですか。

1. A異なる部分木の同じ深さにあるノード
2. B子をもたないノード
3. Cあるノードとその親
4. D同じ親をもつノード

木において、葉（leaf）とは何ですか。

1. A親をもたないノード
2. Bちょうど 1 つの子をもつノード
3. C最大の値をもつノード
4. D子をもたないノード

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

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

ある二分木の根は 1 で、左の子が 2、右の子が 3 です。ノード 2 の子は 4（左）と 5（右）です。帰りがけ順の走査はどれですか。

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D5 4 3 2 1

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

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

配列のサイズ k のすべてのウィンドウの最大値を合計 O(n) で計算できる構造はどれですか。

1. Aウィンドウの要素の単方向連結リスト
2. Bウィンドウごとに作り直す最小ヒープ
3. C値の降順にインデックスを保持するデック
4. Dずらすことで更新するソート済み配列

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

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