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

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

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

配列の要素はメモリにどのように格納されますか。

1. Aばらばらに、ポインタでつながれて
2. Bメモリページの木の中に
3. Cハッシュで選ばれたランダムな位置に
4. D1 つの連続したブロックに、順に並んで

優先度付きキューの実装に一般的に使われる構造はどれですか。

1. Aスタック
2. Bヒープ
3. C文字列
4. D順序のない単方向連結リスト

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

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

AVL 木と赤黒木が保証するものは何ですか。

1. Aどの場合でも定数時間での探索
2. B再平衡化による O(log n) の高さ
3. C2 つの子を持つノードが存在しないこと
4. Dキーが挿入順に格納されること

ダイクストラ法が次に処理する頂点を選ぶために使う抽象データ型はどれですか。

1. Aスタック
2. B順序のない集合
3. CFIFO キュー
4. D最小優先度付きキュー

O(1) の追加メモリで、単方向連結リストが閉路を含むかどうかを検出するにはどうすればよいですか。

1. A訪問したすべてのノードをハッシュ集合に格納する
2. B一方のポインタを 1 歩ずつ、もう一方を 2 歩ずつ進め、出会うかどうかを調べる
3. Cリストをソートして重複を探す
4. D数がリストの長さのフィールドを超えるまでノードを数える

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

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