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

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

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

ハッシュテーブルはデータをどのような形で格納しますか。

1. Aハッシュ関数で位置が決まるキーと値のペア
2. B固定長の文字列
3. Cキーが順序付けられた木
4. Dソート済みリストのみ

n 個のノードをもつ木には何本の辺がありますか。

1. An + 1
2. Bn − 1
3. C2n
4. Dn

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

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

サイズ 7 のハッシュテーブルが h(k) = k mod 7 と線形探査法を使っています。10 を挿入した後、17 はどこに格納されますか。

1. Aインデックス 6
2. Bインデックス 0
3. Cインデックス 3
4. Dインデックス 4

隣接行列を使って辺 (u, v) が存在するかを調べるのにどれだけ時間がかかりますか。

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

クラスカルの最小全域木アルゴリズムで、union-find 構造は何に使われますか。

1. A探索中に、各頂点の始点からの現在の距離を格納する
2. B辺の両端点がすでにつながっているかどうかを調べる
3. C開始頂点を選ぶ
4. D辺を重みの順にソートする

基数木（radix tree、圧縮トライ）は通常のトライをどのように改良していますか。

1. A各単語の最初の文字だけを保持する
2. B各ノードの子を頻度順にソートする
3. C子が 1 つだけのノードの連なりを、文字列でラベル付けされた 1 本の辺にまとめる
4. D各単語を別々のノードではなく、根にあるハッシュテーブルに格納する