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

グラフは何で構成されていますか。

1. Aキーとハッシュ値のみ
2. B辺（edge）で結ばれた頂点（vertex、ノード）
3. C行と列
4. D根と葉のみ

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

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

キューの先頭の要素を取り除く操作の名前は何ですか。

1. Aインサート（Insert）
2. Bプッシュ（Push）
3. Cデキュー（Dequeue）
4. Dエンキュー（Enqueue）

深さ優先探索（反復版）で使われるデータ構造はどれですか。

1. Aハッシュテーブルのみ
2. Bキュー
3. Cスタック
4. Dヒープ

配列に格納された二分最小ヒープ（インデックスは 0 から）において、インデックス i のノードの子はどこにありますか。

1. A2i と 2i + 1
2. B2i + 1 と 2i + 2
3. Ci/2 と i/2 + 1
4. Di + 1 と i + 2

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

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

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

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

赤黒木の規則は、n 個のキーをもつ木の高さについてどのような保証を与えますか。

1. A高さは高々 log₂ n + 1 である
2. B高さはちょうど log₂ n である
3. C高さは高々 n / 2 である
4. D高さは高々 2 log₂(n + 1) である