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

無向グラフにおいて、頂点の次数（degree）とは何ですか。

1. Aその頂点につながっている辺の数
2. Bその頂点からの最長経路の長さ
3. C隣接リストにおけるその位置
4. Dグラフの頂点の数

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

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

木において、葉（leaf）とは何ですか。

1. Aちょうど 1 つの子をもつノード
2. B子をもたないノード
3. C親をもたないノード
4. D最大の値をもつノード

平衡二分探索木でキーを探索する時間計算量はどれですか。

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

AVL 木と赤黒木が保証するものは何ですか。

1. Aキーが挿入順に格納されること
2. B再平衡化による O(log n) の高さ
3. C2 つの子を持つノードが存在しないこと
4. Dどの場合でも定数時間での探索

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

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

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

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

異なるキーをもつ二分木を常に一意に決定する走査の組はどれですか。

1. A行きがけ順と帰りがけ順
2. B行きがけ順だけ
3. Cレベル順だけ
4. D行きがけ順と通りがけ順