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

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

長さ m と n の文字列の最長共通部分列を求める標準的な動的計画法の時間計算量は何ですか？

  1. AO(mn log n)
  2. BO(mn)
  3. CO(m + n)
  4. DO(2m+n)
2.アルゴリズムと計算量むずかしい

一部の辺の重みが負のとき、ダイクストラ法が誤った結果を出すことがあるのはなぜですか？

  1. A負の辺があるたびに無限ループに陥るから
  2. B無向グラフでしか動作しないから
  3. C負の数は優先度付きキューに格納できないから
  4. D頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから
3.データ構造ふつう

二分探索木で最小のキーはどのように見つけますか。

  1. A根から左の子がなくなるまで左の子をたどる
  2. B根から右の子がなくなるまで右の子をたどる
  3. C根だけを見る
  4. Dすべての葉を訪問して比べる
4.データ構造むずかしい

ハッシュテーブルが正しく動作するためには、ハッシュと等価性はどの規則に従わなければなりませんか。

  1. Aハッシュ値が等しければキーも等しい
  2. B異なるキーは異なるハッシュ値をもたなければならない
  3. C等しいキーは等しいハッシュ値をもたなければならない
  4. Dハッシュ値は素数でなければならない
5.グラフ理論ふつう

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

|V| = 15|E| = 26
k =
6.グラフ理論むずかしい
ABCDEF

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

M = 隣接行列L = 2
N =

3溶液

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

答え: B · O(mn)

これが答えになる理由

表には (m + 1)(n + 1) 個のセルがあり、各セルは隣接するセルから O(1) で計算されます。

答え

B · O(mn)
2.アルゴリズムと計算量

答え: D · 頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから

これが答えになる理由

貪欲なステップは、取り出した距離が確定するように重みが非負であることに依存しています。重みが負になりうる場合はベルマン－フォード法を使います。

答え

D · 頂点は取り出された時点で確定するが、後の負の辺によってより短い経路が得られる可能性があるから
3.データ構造

答え: A · 根から左の子がなくなるまで左の子をたどる

これが答えになる理由

最も左のノードより小さいキーは木の中にないので、それが最小値です。コストは高さに比例します。

答え

A · 根から左の子がなくなるまで左の子をたどる
4.データ構造

答え: C · 等しいキーは等しいハッシュ値をもたなければならない

これが答えになる理由

等しい 2 つのキーのハッシュが異なれば、それらは異なるバケットに格納され、検索に失敗します。等しくないキーがハッシュを共有することはかまいません。

答え

C · 等しいキーは等しいハッシュ値をもたなければならない
5.グラフ理論

答え: k = 12

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

全域木の辺

15 − 1 = 14

取り除く辺

k = 26 − 14 = 12

答え

k = 12
6.グラフ理論

答え: N = 1

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

隣接行列

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

共通の隣接頂点

(M²)EB = 0·1 + 0·0 + 1·1 + 1·0 + 0·0 + 1·0 = 1

答え

N = 1

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