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

配列では O(1) だが、単方向連結リストでは O(n) となる操作はどれですか。

1. A先頭の要素の削除
2. B最初の要素の読み取り
3. Cインデックス i の要素へのアクセス
4. D先頭への挿入

無向グラフにおいて、頂点の次数（degree）とは何ですか。

1. A隣接リストにおけるその位置
2. Bその頂点からの最長経路の長さ
3. Cその頂点につながっている辺の数
4. Dグラフの頂点の数

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

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

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

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

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

1. A二次探査法（Quadratic probing）
2. Bダブルハッシュ法（Double hashing）
3. Cチェイン法（Separate chaining）
4. D線形探査法（Linear probing）

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

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

ダブルハッシュ法が主に軽減する線形探査法の問題はどれですか。

1. Aハッシュ関数が必要であること
2. Bキーの値を読み取る O(n) のコスト
3. Cキーをテーブルに格納する必要があること
4. D使用中のスロットが長く連なる一次クラスタリング

標準的なブルームフィルタから、ビットをクリアするだけで要素を削除できないのはなぜですか。

1. Aブルームフィルタは要素全体を格納しており、いったんハッシュ化されると再び見つけられないから
2. Bそれらのビットは他の要素にも属している可能性があり、偽陰性を引き起こすから
3. Cブルームフィルタのビットは作成後に変更できないから
4. D削除すると偽陽性率が 100% に上がるから