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

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

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

木の高さは一般にどのように定義されますか。

1. A根の子の数
2. B根と葉をすべて含めた、木に含まれるノードの総数
3. C木の葉の数
4. D根から葉までの最も長い経路上の辺の数

静的配列と動的配列の主な違いは何ですか。

1. A静的配列はインデックスによるアクセスが遅い
2. B動的配列は要素を連結されたノードに格納するので、1 つずつ拡張できる
3. C静的配列は数値しか格納できない
4. D動的配列は、より大きなメモリブロックに移ることで拡張できる

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

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

同じ長さの連結リストを走査するより、配列を走査する方が実際にはずっと速いことが多いのはなぜですか。

1. A配列の走査は全体で O(1)、連結リストの走査は O(n) だから
2. B連結リストは常に要素をディスクに格納するから
3. C配列の要素は連続しているので、CPU キャッシュを有効に使えるから
4. D配列では値を比較する命令が少なくて済むから

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

1. A(i − 1) mod n
2. Bi + 1
3. C(i + 1) mod n
4. D2i + 1

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

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

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

1. A異なるキーは異なるハッシュ値をもたなければならない
2. Bハッシュ値が等しければキーも等しい
3. Cハッシュ値は素数でなければならない
4. D等しいキーは等しいハッシュ値をもたなければならない