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

公式集、全トピックの解法の要点、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.アルゴリズムと計算量ふつう

動的計画法（dynamic programming）が有効なのは、問題が次の性質を持つときです。

  1. Aループが一つだけ
  2. Bランダムな入力のみ
  3. C重複する部分問題と最適部分構造
  4. D部分問題がまったくないので、1 ステップで解ける
2.アルゴリズムと計算量むずかしい

どんな入力に対してもクイックソートの期待（expected）実行時間を O(n log n) にする手法はどれですか？

  1. A常に先頭の要素を選ぶ
  2. B左側にのみ再帰を使う
  3. Cピボットを一様ランダムに選ぶ
  4. Dクイックソートを実行する前に入力をソートする
3.データ構造ふつう

ある道路網には 100,000 の交差点があり、それぞれが約 4 つの他の交差点とつながっています。最も適した表現はどれですか。

  1. A隣接リスト
  2. B頂点の 1 つのソート済み配列
  3. C隣接行列
  4. D辺の二分ヒープ
4.データ構造むずかしい

赤黒木が満たさなければならない性質はどれですか。

  1. Aすべての赤ノードの子は赤でなければならないので、赤ノードは葉まで途切れなく連なる
  2. Bすべてのノードが赤でなければならない
  3. Cあるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい
  4. D根は赤でなければならない
5.グラフ理論ふつう

連結グラフに 13 個の頂点と 13 本の辺があります。全域木にするには、辺を何本k取り除く必要がありますか？

|V| = 13|E| = 13
k =
6.グラフ理論むずかしい
41326175121820ABCDEFG

クラスカル法は最小全域木をつくります。それが 4 番目に加える辺をクリックしてください。飛ばされた辺は数えません。

k = 4
  1. 1辺 AB
  2. 2辺 BC
  3. 3辺 BD
  4. 4辺 DE
  5. 5辺 DF
  6. 6辺 GB
  7. 7辺 GC
  8. 8辺 GD
  9. 9辺 GE

3溶液

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

答え: C · 重複する部分問題と最適部分構造

これが答えになる理由

重複する部分問題の結果を保存する（メモ化または表計算）ことで繰り返しの処理を避け、指数時間のアルゴリズムを多項式時間に変えられます。

答え

C · 重複する部分問題と最適部分構造
2.アルゴリズムと計算量

答え: C · ピボットを一様ランダムに選ぶ

これが答えになる理由

ランダムなピボットを使うと、すべての入力に対して期待実行時間は O(n log n) になります。悪いケースは依然として存在しますが、起こる確率は非常に低くなります。

答え

C · ピボットを一様ランダムに選ぶ
3.データ構造

答え: A · 隣接リスト

これが答えになる理由

行列では 1010 個のセルが必要になり、そのほとんどが空です。隣接リストなら約 400,000 個の辺の項目だけを格納すれば済みます。

答え

A · 隣接リスト
4.データ構造

答え: C · あるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい

これが答えになる理由

赤黒木の規則：ノードは赤か黒、根は黒、赤ノードの子は黒、すべての経路の黒高さが等しい。これにより高さは ≤ 2 log₂(n + 1) に保たれます。

答え

C · あるノードからその子孫の葉までのすべての経路に含まれる黒ノードの数が等しい
5.グラフ理論

答え: k = 1

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

全域木の辺

13 − 1 = 12

取り除く辺

k = 13 − 12 = 1

答え

k = 1
6.グラフ理論

答え: 辺 DE

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

クラスカル法

1. BD (2)
2. AB (4)
3. GB (5)
4. DE (6)
5. GC (12)
6. DF (17)

辺の番号 4

DE

答え

辺 DE

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