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

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

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

抽象データ型としての集合（set）を定義する特徴は何ですか。

1. Aキーと値の組を格納する
2. B要素をソート順に格納する
3. C一方の端でだけアクセスを許す
4. D重複なしに要素を格納する

単方向連結リストでは、最後のノードの next ポインタには何が入っていますか。

1. A最初のノードのアドレス
2. Bnull（ノードなし）
3. C前のノードのアドレス
4. Dリストのノードの数

二分探索木で最小のキーはどのように見つけますか。

1. A根から右の子がなくなるまで右の子をたどる
2. Bすべての葉を訪問して比べる
3. C根だけを見る
4. D根から左の子がなくなるまで左の子をたどる

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

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

2 つのスタックでキューを実装します。「in」スタックに push し、「out」スタックから pop し、「out」が空になったら「in」から補充します。1 回の操作あたりのならしコストはどれですか。

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

隣接行列として格納された V 頂点のグラフに対する幅優先探索の実行時間はどれですか。

1. AO(V)
2. BO(V + E)
3. CO(E log V)
4. DO(V²)

トポロジカルソートのためのカーンのアルゴリズムは、入次数 0 の頂点を繰り返し取り除きます。それらの頂点を保持する構造はどれですか。

1. A訪問したすべての辺のスタック
2. Bどの頂点がすでに取り除かれたかを記録する隣接行列
3. C入次数が 0 の頂点のキュー（または任意のコレクション）
4. D出次数で順序づけた最大ヒープ