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

二分探索木において、あるノードの左部分木にある値はどうなっていますか。

1. Aそのノードの値と等しい
2. Bそのノードの値より小さい
3. Cそのノードの値より大きい
4. Dランダムな順序

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

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

グラフは何で構成されていますか。

1. A根と葉のみ
2. B辺（edge）で結ばれた頂点（vertex、ノード）
3. Cキーとハッシュ値のみ
4. D行と列

トライ（接頭辞木）が特に効率的なのはどのような用途ですか。

1. A最短経路の探索
2. B行列の格納
3. Cオートコンプリートなどの接頭辞検索
4. D数値のソート

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

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

リストの中ほどにあるノードへの参照をもっています。どのリストなら、それを O(1) で削除できますか。

1. A動的配列
2. B双方向連結リスト
3. C単方向連結リスト
4. Dソート済み配列

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

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

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

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