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

公式集、全トピックの解法の要点、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マージソートはすでに O(n) だから
  3. C動的計画法はグラフ問題にしか使えず、配列には使えないから
  4. D部分問題が重複しないので、再利用するものがないから
2.アルゴリズムと計算量むずかしい

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

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

リストの中ほどにあるノードへの参照をもっています。どのリストなら、それを O(1) で削除できますか。

  1. Aソート済み配列
  2. B双方向連結リスト
  3. C単方向連結リスト
  4. D動的配列
4.データ構造むずかしい

n 個の数の配列に対するフェニック木(Binary Indexed Tree)が O(log n) でサポートする操作はどれですか。

  1. A任意の位置への要素の挿入
  2. B配列のソートと二分探索
  3. CO(1) での中央値の検索
  4. D接頭辞和のクエリと単一要素の更新
5.グラフ理論ふつう
ABCDEFオイラー閉路オイラー路あり、閉路なしどちらでもない

この連結グラフには、オイラー閉路、閉路でないオイラー路、またはどちらもないのうち、どれがありますか? 答えをクリックしてください。

|V| = 6|E| = 8
  1. 1オイラー閉路
  2. 2オイラー路あり、閉路なし
  3. 3どちらでもない
6.グラフ理論むずかしい
ABCDE

E から D への長さ 3 の歩道はいくつありますか? 歩道では頂点や辺を繰り返してもかまいません。その数を N とします。

M = 隣接行列L = 3
N =

3溶液

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

答え: D · 部分問題が重複しないので、再利用するものがないから

これが答えになる理由

マージソートの 2 つの半分は互いに素で、それぞれ一度だけ解かれます。DP が役立つのは、フィボナッチのように部分問題が繰り返し現れる場合だけです。

答え

D · 部分問題が重複しないので、再利用するものがないから
2.アルゴリズムと計算量

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

これが答えになる理由

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

答え

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

答え: B · 双方向連結リスト

これが答えになる理由

双方向連結リストのノードは前のノードを知っているので、prev と next を直接つなぎ直せます。単方向連結リストでは前のノードを探さなければなりません。

答え

B · 双方向連結リスト
4.データ構造

答え: D · 接頭辞和のクエリと単一要素の更新

これが答えになる理由

フェニック木は各インデックスの下位ビットによって決まる範囲の部分和を格納するので、接頭辞和と一点更新のどちらも O(log n) で済みます。

答え

D · 接頭辞和のクエリと単一要素の更新
5.グラフ理論

答え: オイラー路あり、閉路なし

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

次数

deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 2, deg(E) = 4, deg(F) = 2

奇数次数の頂点

B, C → 2
オイラー路あり、閉路なし

答え

オイラー路あり、閉路なし

オイラー路は、一方の奇数次数の頂点から始まり、他方で終わります。

6.グラフ理論

答え: N = 3

次数:頂点の次数は、その頂点に接する辺の数です。どの辺にも端が 2 つあるので、次数の和は辺の数の 2 倍になります:Σ deg(v) = 2|E|(握手補題)。したがって、奇数次数の頂点の数は偶数です。Kn には n(n − 1)/2 本の辺があり、n 個の頂点をもつ k 正則グラフには nk/2 本、n 個の頂点をもつ木には n − 1 本の辺があります。

隣接行列

A: 0 1 1 0 0
B: 1 0 1 0 1
C: 1 1 0 0 1
D: 0 0 0 0 1
E: 0 1 1 1 0

もう 1 歩

(M³)ED = 2·0 + 1·0 + 1·0 + 0·0 + 3·1 = 3

答え

N = 3

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