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

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

1. A2n
2. Bn − 1
3. Cn + 1
4. Dn

二分木を定義するものは何ですか。

1. Aすべてのノードが高々 2 つの子をもつ
2. Bすべてのノードが 2 進数を格納する
3. Cすべてのノードがちょうど 2 つの子をもつ
4. D木がちょうど 2 つのレベルをもつ

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

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

「{[()]}」の括弧の対応がとれているかを調べるのに使われるデータ構造はどれですか。

1. A二分探索木
2. Bスタック
3. Cハッシュテーブル
4. Dキュー

高さを辺の数で数えるとき、高さ h の完全（perfect）二分木にはいくつのノードがありますか。

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

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

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

配列のサイズ k のすべてのウィンドウの最大値を合計 O(n) で計算できる構造はどれですか。

1. A値の降順にインデックスを保持するデック
2. Bずらすことで更新するソート済み配列
3. Cウィンドウごとに作り直す最小ヒープ
4. Dウィンドウの要素の単方向連結リスト

ランクによる合併（union by rank）も経路圧縮も使わない場合、n 要素の union-find 構造での 1 回の find の最悪コストはどれですか。

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