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

公式集、全トピックの解法の要点、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挿入ソートは最悪の場合 O(n log n) だから
  2. B大きな入力では、挿入ソートは他のどのソートアルゴリズムよりメモリが少なくて済むから
  3. C再帰アルゴリズムは 10 要素未満の配列を扱えないから
  4. D挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
2.アルゴリズムと計算量むずかしい

クラス NP の定義として正しいものはどれですか？

  1. A多項式でない問題
  2. B多項式時間で解けない問題
  3. C証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
  4. Dどのアルゴリズムでも解けない問題
3.データ構造ふつう

連結リストにおける番兵（ダミー）ノードの目的は何ですか。

  1. Aリストをソートされた状態にする
  2. B先頭や末尾での特別な場合をなくしてコードを単純にする
  3. C要素の数を格納する
  4. Dリストのノード数が決まった最大値を超えて増えないようにする
4.データ構造むずかしい

二分探索木から 2 つの子を持つノードを削除するには、通常どうしますか。

  1. A部分木全体を削除する
  2. Bその下の部分木を一から作り直し、含まれていたすべてのキーを挿入し直す
  3. C中間順の後続ノード（または先行ノード）で置き換え、そのノードを削除する
  4. D根と入れ替える
5.グラフ理論ふつう

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

4 × deg 34 × deg 44 × deg 5
L =
6.グラフ理論むずかしい
15681061513215ABCDEFG

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

始点：A終点：D
d(D) =

3溶液

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

答え: D · 挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから

これが答えになる理由

n が小さいときは、O(n²) であっても、挿入ソートの単純なループの方がクイックソートやマージソートの再帰のオーバーヘッドより速くなります。

答え

D · 挿入ソートはオーバーヘッドが小さく、小さな入力やほぼソート済みの入力で速いから
2.アルゴリズムと計算量

答え: C · 証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題

これが答えになる理由

NP の問題では、たとえば与えられた割り当てがブール式を充足することの確認のように、提案された解（証拠）をすばやく検証できます。

答え

C · 証拠（certificate）が与えられれば、「はい」の答えを多項式時間で検証できる決定問題
3.データ構造

答え: B · 先頭や末尾での特別な場合をなくしてコードを単純にする

これが答えになる理由

番兵があれば実際のすべてのノードに前のノードがあるので、先頭での挿入や削除に特別な処理が不要になります。

答え

B · 先頭や末尾での特別な場合をなくしてコードを単純にする
4.データ構造

答え: C · 中間順の後続ノード（または先行ノード）で置き換え、そのノードを削除する

これが答えになる理由

中間順の後続ノードは子を高々 1 つしか持たないため、そのキーを削除対象のノードにコピーした後、簡単に削除できます。

答え

C · 中間順の後続ノード（または先行ノード）で置き換え、そのノードを削除する
5.グラフ理論

答え: L = 26

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

木の握手補題

L + 48 = 2(L + 12) − 2
L = 26

答え

L = 26

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

6.グラフ理論

答え: d(D) = 29

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

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

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

A (0): C: 15
C (15): B: 21, G: 28
B (21): D: 29
G (28): E: 43
D (29): E: 39, F: 35
F (35)
E (39)

最短経路

A → C → B → D
d(D) = 29

答え

d(D) = 29

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