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

重み付きグラフとは何ですか。

1. Aディスクに格納されたグラフ
2. B頂点より辺の方が多いグラフ
3. C辺の数が多いために、一部の頂点が他の頂点より重くなっているグラフ
4. D各辺がコストや距離などの数値をもつグラフ

二分最小ヒープの最小の要素はどこにありますか。

1. A最も左の葉
2. Bいずれかの葉にあり、探さなければならない
3. C根
4. D配列の最後の位置

スタックに対する peek（または top）操作は何をしますか。

1. A一番上の要素を取り除かずに返す
2. Bスタックからすべての要素を取り除く
3. C一番上の要素を取り除いて返す
4. Dスタックの一番下の要素を返す

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

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

無向グラフの隣接行列について正しいのはどれですか。

1. A主対角線には常に 1 が入っている
2. B主対角線に関して対称である
3. C各行にちょうど 1 つの 1 がある
4. D常に上三角行列である

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

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

配列のサイズ k のすべてのウィンドウの最大値を合計 O(n) で計算できる構造はどれですか。

1. Aウィンドウの要素の単方向連結リスト
2. Bずらすことで更新するソート済み配列
3. Cウィンドウごとに作り直す最小ヒープ
4. D値の降順にインデックスを保持するデック

ランクによる併合（union by rank）と経路圧縮（path compression）を用いた union-find（素集合）構造の、1 操作あたりの償却コストはどれですか。

1. AO(α(n))（逆アッカーマン関数）で、実用上は定数
2. Bちょうど O(log n)
3. CO(n)
4. DO(n²)