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

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

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

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

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

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

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

負荷率がしきい値を超えた後にハッシュテーブルが再ハッシュ（rehash）すると、何が起こりますか。

1. A既存のキーがその場でソートされる
2. B衝突しているキーだけが、テーブルの末尾にある新しいオーバーフローリストに移される
3. C場所を空けるために最も古いキーが削除される
4. Dより大きなテーブルが確保され、すべてのキーが挿入し直される

ある道路網には 100,000 の交差点があり、それぞれが約 4 つの他の交差点とつながっています。最も適した表現はどれですか。

1. A辺の二分ヒープ
2. B隣接リスト
3. C隣接行列
4. D頂点の 1 つのソート済み配列

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

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

n 要素の二分最小ヒープで任意のキーを探索するのにどれだけ時間がかかりますか。

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

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

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