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

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

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

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

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

配列では遅いが、連結リストの先頭では速い操作はどれですか。

1. A先頭への挿入
2. Bインデックスによる最後の要素の読み取り
3. C5 番目の要素へのアクセス
4. D固定長配列の長さの取得

AVL 木はすべてのノードでどのような平衡条件を保っていますか。

1. Aすべてのノードが赤または黒に塗られている
2. B左右の部分木の高さの差が高々 1 である
3. Cすべての葉がちょうど同じ深さにある
4. Dすべてのノードの両方の部分木が、まったく同じ数のノードを含む

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

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

n 要素の配列の中央に要素を挿入するコストはどれですか。

1. A各要素が n 回移動するので O(n²)
2. Bインデックスがわかっているので O(1)
3. C後ろの要素をずらさなければならないので O(n)
4. D二分探索のため O(log n)

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

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

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

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