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

最大ヒープ性（max-heap property）とは何ですか。

1. Aすべての親のキーがその子のキー以上である
2. Bすべての葉が最大のキーをもつ
3. Cキーが左から右へソートされている
4. Dすべての左の子のキーが右の兄弟のキー以上である

双方向連結リストの各ノードには何が含まれていますか。

1. Aデータの 2 つのコピーと 1 つのポインタ
2. Bデータと次のノードへのポインタだけ
3. Cデータ、次のノードへのポインタ、前のノードへのポインタ
4. Dデータと 2 つのポインタ（次のノードへのものと、その次のノードへのもの）

木におけるノードの深さとは何ですか。

1. Aそのノードから最も深い葉までの辺の数
2. B根からそのノードまでの辺の数
3. Cそのノードの子の数
4. Dその部分木に含まれるノードの数

無向グラフの隣接行列について正しいのはどれですか。

1. A主対角線に関して対称である
2. B各行にちょうど 1 つの 1 がある
3. C常に上三角行列である
4. D主対角線には常に 1 が入っている

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

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

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

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

オープンアドレス法を使うハッシュテーブルで、削除に「墓標」（tombstone）マーカーがよく使われるのはなぜですか。

1. A墓標がハッシュ計算を高速化するから
2. B安全のため削除したキーを永久に保持する必要があり、スロットを再利用できないから
3. Cテーブルがソートされた状態になるから
4. Dスロットを空にすると、他のキーの探査列が途切れる可能性があるから

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

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