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

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

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

二分木を定義するものは何ですか。

1. Aすべてのノードが 2 進数を格納する
2. Bすべてのノードがちょうど 2 つの子をもつ
3. Cすべてのノードが高々 2 つの子をもつ
4. D木がちょうど 2 つのレベルをもつ

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

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

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

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

二分最小ヒープの extract-min はどのように動作しますか。

1. A最後の要素を根に移し、下へ移動させる（sift down）
2. Bすべての葉から新しい最小値を探す
3. C根を取り除き、すべての要素を 1 つ左にずらす
4. D配列の最後の要素を取り除く

高さを辺の数で数えるとき、高さ h の完全（perfect）二分木にはいくつのノードがありますか。

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

循環バッファでは、front == rear は空と満杯のどちらも意味しえます。これらを区別する一般的な方法はどれですか。

1. A要素数を別に保持するか、常に 1 つのスロットを使わずに残しておく
2. Bfront と rear が等しいときは常にバッファをクリアして、空の状態にする
3. Cバッファのサイズを 2 のべき乗にする
4. Dfront と rear を同じ変数に格納する

サーバーがハッシュ関数を万能（universal）族からランダムに選ぶのはなぜですか。

1. Aハッシュテーブルをソートされた状態にするため
2. B攻撃者がすべて衝突する多数のキーを選べる可能性をきわめて低くするため
3. Cテーブルのサイズを変更する必要をなくすため
4. D攻撃者がどのようなキーを送っても、2 つのキーが決して衝突しないことを保証するため