データ構造とアルゴリズム：直前対策パック

公式集、全トピックの解法の要点、6 問の演習問題。完全な解答は巻末にあります。

新しい問題科目に戻る

印刷ウィンドウで「PDF として保存」を選ぶと、コピーを端末に保存できます。

1公式と解法

グラフ理論

握手補題
Σ deg(v) = 2|E|
完全グラフ
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
正則グラフ
|E| = n·k/2
木と森
|E| = n − 1, |E| = n − c
木の葉
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
オイラー
閉路：すべての次数が偶数； 路：奇数次数がちょうど 2 つ
Kn のハミルトン閉路
(n − 1)!/2
ダイクストラ法の更新
d(v) = min(d(v), d(u) + w(u, v))
長さ L の歩道
(Mᴸ)ij

解き方

  1. 各頂点の次数を書き出します。次数の総和は辺の数の 2 倍になります。
  2. オイラーの問題では、グラフが連結であることを確かめ、奇数次数の頂点を数えます。
  3. 木では、辺が n − 1 本であることと握手補題を使います。
  4. ダイクストラ法では、暫定距離の表をつくり、毎回、未確定の頂点のうち最小のものを確定します。
  5. 最小全域木では、辺を重みの順に並べ、閉路をつくる辺を飛ばす方法（クラスカル法）か、始点から 1 本の木を成長させる方法（プリム法）を使います。

2演習問題

1.アルゴリズムと計算量ふつう

プリム法は最小全域木をどのように構築しますか？

  1. A開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
  2. Bすべての辺を重みでソートし、森の中で閉路をつくる場合を除いて 1 本ずつ加える
  3. C閉路がなくなるまで最も高い辺を取り除く
  4. D幅優先探索を実行し、BFS 木を残す
2.アルゴリズムと計算量むずかしい

新しい問題 X が NP 困難であることを示すには、何をしなければなりませんか？

  1. A既知の NP 困難な問題を多項式時間で X に帰着させる
  2. BX には小さな入力に対する多項式アルゴリズムがないことを示す
  3. CX を多項式時間で検証できることを示す
  4. DX を多項式時間で既知の NP 困難な問題に帰着させる
3.データ構造ふつう

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

  1. AO(n log n)
  2. BO(n)
  3. CO(log n)
  4. DO(1)
4.データ構造むずかしい

サーバーがハッシュ関数を万能（universal）族からランダムに選ぶのはなぜですか。

  1. A攻撃者がすべて衝突する多数のキーを選べる可能性をきわめて低くするため
  2. B攻撃者がどのようなキーを送っても、2 つのキーが決して衝突しないことを保証するため
  3. Cハッシュテーブルをソートされた状態にするため
  4. Dテーブルのサイズを変更する必要をなくすため
5.グラフ理論ふつう

木に 次数 5 の頂点が 4 個, 次数 2 の頂点が 2 個 があり、ほかのすべての頂点は葉（次数 1）です。葉は何枚Lありますか？

4 × deg 52 × deg 2
L =
6.グラフ理論むずかしい
34212132011ABCDE

プリム法は、頂点 E から始めて最小全域木をつくります。それが 2 番目に加える辺をクリックしてください。

始点：Ek = 2
  1. 1辺 AB
  2. 2辺 AC
  3. 3辺 BC
  4. 4辺 BD
  5. 5辺 CE
  6. 6辺 DE
  7. 7辺 BE

3溶液

1.アルゴリズムと計算量

答え: A · 開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える

これが答えになる理由

木をまたぐ辺の優先度付きキューを用いるプリム法は、二分ヒープを使うと O(E log V) で動作します。

答え

A · 開始頂点から 1 本の木を成長させ、木から出る最も安い辺を加える
2.アルゴリズムと計算量

答え: A · 既知の NP 困難な問題を多項式時間で X に帰着させる

これが答えになる理由

既知の困難な問題を効率よく X に変換できれば、X に対する高速なアルゴリズムは既知の問題も解くことになります。

答え

A · 既知の NP 困難な問題を多項式時間で X に帰着させる
3.データ構造

答え: C · O(log n)

これが答えになる理由

平衡木の高さは約 log₂ n なので、探索は根から葉への 1 本の経路をたどるだけです。

答え

C · O(log n)
4.データ構造

答え: A · 攻撃者がすべて衝突する多数のキーを選べる可能性をきわめて低くするため

これが答えになる理由

万能ハッシュでは、攻撃者はどの関数が選ばれたかを知らないので、どのようなキーの集合についても衝突の期待数は小さくなります。

答え

A · 攻撃者がすべて衝突する多数のキーを選べる可能性をきわめて低くするため
5.グラフ理論

答え: L = 14

オイラー、ハミルトン、木：連結グラフは、すべての頂点の次数が偶数のときオイラー閉路（すべての辺を 1 回ずつ通って始点に戻る）をもち、ちょうど 2 つの頂点の次数が奇数のとき、閉路でないオイラー路をもちます。その路は、一方の奇数次数の頂点から他方へ通ります。ハミルトン閉路はすべての頂点を 1 回ずつ訪れ、Kn には (n − 1)!/2 個あります。n 個の頂点をもつ木には n − 1 本の辺があり、m 本の辺をもつ連結グラフは、m − n + 1 本の辺を取り除いても全域木が残ります。

木の握手補題

L + 24 = 2(L + 6) − 2
L = 14

答え

L = 14

近道：次数 d ≥ 3 の頂点について L = 2 + Σ (d − 2) です。

6.グラフ理論

答え: 辺 BC

最短経路と全域木：ダイクストラ法は毎ラウンド 1 つの頂点を確定します：暫定距離が最小の未確定の頂点です。その距離は最終となり、各隣接頂点 v は d(v) = min(d(v), d(u) + w(u, v)) と更新されます。クラスカル法は、辺を軽い順に取り、閉路をつくる辺を飛ばして最小全域木をつくります。プリム法は、始点から 1 本の木を成長させ、その木から出る最も軽い辺を常に加えます。n 個の頂点の全域木には n − 1 本の辺があります。

プリム法

1. BE (11)
2. BC (2)
3. AB (3)
4. BD (12)

辺の番号 2

BC

答え

辺 BC

ExamProblems · examproblems.com/courses/data-structures-and-algorithms