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

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

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

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

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

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

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

二分ヒープをポインタなしで配列に格納できるのはなぜですか。

1. Aヒープは 100 個を超える要素を含むことがないから
2. B完全二分木なので、位置が単純なインデックスの式に従うから
3. Cヒープのすべてのキーは等しいから
4. D配列は自動的にキーをソート順に保つので、ポインタが不要になるから

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

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

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

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

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

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

データベースやファイルシステムで B 木が使われるのはなぜですか。

1. Aデータをソートせずに格納するから
2. B再平衡化が不要だから
3. C分岐数が大きいため木が浅く保たれ、遅いディスク読み込みが減るから
4. Dどの配列よりもメモリ使用量が少ないので、索引全体が常に主記憶に収まるから