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

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

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

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

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

二分探索木において、あるノードの左部分木にある値はどうなっていますか。

1. Aランダムな順序
2. Bそのノードの値と等しい
3. Cそのノードの値より大きい
4. Dそのノードの値より小さい

固定のアルファベットをもつトライで、長さ L の単語を探索するのにどれだけ時間がかかりますか。

1. A単語の数を n として O(log n)
2. BO(L × n)
3. C格納されている単語の数に関係なく O(L)
4. D単語の数を n として O(n)

後置記法の式 3 4 + 2 * の値は何ですか。

1. A14
2. B10
3. C11
4. D24

V 個の頂点と E 本の辺をもつグラフについて、隣接リストはどれだけのメモリを使いますか。

1. AO(V + E)
2. BO(E²)
3. CO(V × E)
4. DO(V²)

単純一様ハッシュの仮定の下で、n 個のキーと m 個のバケットをもつチェイン法のハッシュテーブルの探索の期待時間はどれですか。

1. AO(n)
2. BO(log n)
3. CO(m)
4. Dα = n / m として O(1 + α)

ブルームフィルタは「この要素は集合に含まれるか」という問いにどのように答えますか。

1. A常に正確な答えを返す
2. B偽陰性はあり得るが、偽陽性はない
3. C偽陽性はあり得るが、偽陰性はない
4. D数値に対してのみ答えられる