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

公式集、全トピックの解法の要点、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最も早く始まる活動を選ぶ
  2. B重なりの最も少ない活動を先に選び、両立する活動で繰り返す
  3. C最も早く終わる活動を選び、両立する活動で繰り返す
  4. D最も短い活動から選ぶ
2.アルゴリズムと計算量むずかしい

トポロジカルソートが可能なのは、次のどのグラフだけですか?

  1. A有向非巡回グラフ(DAG)
  2. B無向グラフ
  3. C負の重みを持つグラフ
  4. D完全グラフ
3.データ構造ふつう

同じ長さの連結リストを走査するより、配列を走査する方が実際にはずっと速いことが多いのはなぜですか。

  1. A配列では値を比較する命令が少なくて済むから
  2. B配列の要素は連続しているので、CPU キャッシュを有効に使えるから
  3. C配列の走査は全体で O(1)、連結リストの走査は O(n) だから
  4. D連結リストは常に要素をディスクに格納するから
4.データ構造むずかしい

根が 50、左部分木が 30(子は 20, 40)、右部分木が 70(子は 60, 80)の BST で、通りがけ順の後続ノードを使って根を削除します。新しい根になるキーはどれですか。

  1. A70
  2. B40
  3. C60
  4. D80
5.グラフ理論ふつう

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

|V| = 10|E| = 16
k =
6.グラフ理論むずかしい
254410226139ABCDEFG

ダイクストラ法を使って、重み付きグラフで A から F までの最短経路の長さd(F)を求めてください。

始点:A終点:F
d(F) =

3溶液

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

答え: C · 最も早く終わる活動を選び、両立する活動で繰り返す

これが答えになる理由

最も早い終了時刻を選ぶことは交換論法によって最適であると証明できます。他の規則には反例があります。

答え

C · 最も早く終わる活動を選び、両立する活動で繰り返す
2.アルゴリズムと計算量

答え: A · 有向非巡回グラフ(DAG)

これが答えになる理由

トポロジカル順序が存在するのは、有向グラフに閉路がない場合に限ります。DFS または Kahn のアルゴリズムで O(V + E) で求められます。

答え

A · 有向非巡回グラフ(DAG)
3.データ構造

答え: B · 配列の要素は連続しているので、CPU キャッシュを有効に使えるから

これが答えになる理由

連続したメモリは参照の局所性がよい一方、連結されたノードはばらばらに配置されていることがあり、多くのキャッシュミスを引き起こします。

答え

B · 配列の要素は連続しているので、CPU キャッシュを有効に使えるから
4.データ構造

答え: C · 60

これが答えになる理由

右部分木の最も左のノードは 60 なので、60 が 50 と置き換わり、元の位置からは取り除かれます。先行ノードを使えば 40 になります。

答え

C · 60
5.グラフ理論

答え: k = 7

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

全域木の辺

10 − 1 = 9

取り除く辺

k = 16 − 9 = 7

答え

k = 7
6.グラフ理論

答え: d(F) = 8

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

ダイクストラ法をラウンドごとに

各行:確定した頂点、その最終距離、距離が改善される隣接頂点。

A (0): B: 2, C: 5
B (2): D: 6
C (5): E: 9, G: 11
D (6): F: 8
F (8)
E (9)
G (11)

最短経路

A → B → D → F
d(F) = 8

答え

d(F) = 8

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