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

ハッシュテーブルにおいて、衝突（collision）とは何ですか。

1. A2 つの異なるキーが同じインデックスに対応すること
2. Bテーブルのメモリが不足すること
3. C2 つの等しいキーが 2 回格納されること
4. Dキーをまったくハッシュできないこと

デック（deque、両端キュー）とは何ですか。

1. A優先度順に並べられたキュー
2. B1 つの配列を共有する 2 つの別々のキュー
3. C末尾での削除だけを許すキュー
4. D両端での挿入と削除を許す構造

「先入れ先出し」（FIFO）の原理で動作するデータ構造はどれですか。

1. A二分木（Binary tree）
2. Bヒープ（Heap）
3. Cキュー（Queue）
4. Dスタック（Stack）

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

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

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

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

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

1. A線形探査法（Linear probing）
2. B二次探査法（Quadratic probing）
3. Cチェイン法（Separate chaining）
4. Dダブルハッシュ法（Double hashing）

赤黒木が満たさなければならない性質はどれですか。

1. A根は赤でなければならない
2. Bすべての赤ノードの子は赤でなければならないので、赤ノードは葉まで途切れなく連なる
3. Cあるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい
4. Dすべてのノードが赤でなければならない

n 要素の二分最小ヒープで任意のキーを探索するのにどれだけ時間がかかりますか。

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