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

ハッシュテーブルの負荷率（load factor）とは何ですか。

1. Aこれまでの衝突の数
2. Bディスクからテーブルを読み込むのに必要な時間
3. C格納された要素の数をバケットの数で割ったもの
4. Dバケットの数を、格納されたキーの平均の長さで割ったもの

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

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

双方向連結リストの各ノードには何が含まれていますか。

1. Aデータと 2 つのポインタ（次のノードへのものと、その次のノードへのもの）
2. Bデータの 2 つのコピーと 1 つのポインタ
3. Cデータ、次のノードへのポインタ、前のノードへのポインタ
4. Dデータと次のノードへのポインタだけ

平衡二分探索木でキーを探索する時間計算量はどれですか。

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

容量 n の配列に格納された循環キューで、インデックス i の次の位置はどのように計算されますか。

1. Ai + 1
2. B(i − 1) mod n
3. C2i + 1
4. D(i + 1) mod n

ある二分木の根は 1 で、左の子が 2、右の子が 3 です。ノード 2 の子は 4（左）と 5（右）です。帰りがけ順の走査はどれですか。

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D4 5 2 3 1

ハッシュテーブルが正しく動作するためには、ハッシュと等価性はどの規則に従わなければなりませんか。

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)