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

テキストエディタの「元に戻す」（undo）機能に最も適したデータ構造はどれですか。

1. Aハッシュセット
2. Bグラフ
3. Cスタック
4. Dキュー

ハッシュテーブルにおいて、衝突（collision）とは何ですか。

1. A2 つの異なるキーが同じインデックスに対応すること
2. Bキーをまったくハッシュできないこと
3. Cテーブルのメモリが不足すること
4. D2 つの等しいキーが 2 回格納されること

グラフにおいて、閉路（cycle）とは何ですか。

1. A重みが 0 の辺
2. B辺をもたない頂点
3. C同じ頂点から始まり同じ頂点で終わる経路
4. Dすべての頂点を訪問する経路

二分探索木を中間順（in-order）でたどると、キーはどの順序で訪問されますか。

1. Aレベル順
2. B常に降順
3. C挿入順
4. D昇順

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

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

同じ長さの連結リストを走査するより、配列を走査する方が実際にはずっと速いことが多いのはなぜですか。

1. A連結リストは常に要素をディスクに格納するから
2. B配列の走査は全体で O(1)、連結リストの走査は O(n) だから
3. C配列では値を比較する命令が少なくて済むから
4. D配列の要素は連続しているので、CPU キャッシュを有効に使えるから

二分探索木から 2 つの子を持つノードを削除するには、通常どうしますか。

1. A部分木全体を削除する
2. B中間順の後続ノード（または先行ノード）で置き換え、そのノードを削除する
3. Cその下の部分木を一から作り直し、含まれていたすべてのキーを挿入し直す
4. D根と入れ替える

データベースがインデックスに通常の B 木ではなく B+ 木をよく使うのはなぜですか。

1. AB+ 木は二分の内部ノードを使うので、ディスクの読み取りが減るから
2. Bすべてのレコードが連結された葉にあるので、範囲の走査が効率的になるから
3. CB+ 木は平衡を保つ必要がないから
4. DB+ 木はデータを根にだけ格納するから