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

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

n 要素の配列を一度ソートし、その後 k 回の所属判定クエリに二分探索で答えます。全体のコストは何ですか？

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

ナップサック問題のどの変種で、「重さあたりの価値の順に品物をとる」という貪欲な規則が常に最適解を与えますか？

  1. A品物を必ず丸ごととらなければならない 0/1 ナップサック問題
  2. B品物を分割できる分数ナップサック問題
  3. C両方の変種
  4. Dどちらの変種でもない
3.データ構造ふつう

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

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

ダブルハッシュ法が主に軽減する線形探査法の問題はどれですか。

  1. Aキーをテーブルに格納する必要があること
  2. B使用中のスロットが長く連なる一次クラスタリング
  3. Cキーの値を読み取る O(n) のコスト
  4. Dハッシュ関数が必要であること
5.グラフ理論ふつう
ABCDEオイラー閉路オイラー路あり、閉路なしどちらでもない

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

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

重み付きグラフの最小全域木の重みの合計 W を求めてください。

|V| = 7|E| = 9
W =

3溶液

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

答え: B · O(n log n + k log n)

これが答えになる理由

ソートのコストは O(n log n)、各クエリは O(log n) です。k が大きいとき、これは k 回の線形走査（O(nk)）より優れています。

答え

B · O(n log n + k log n)
2.アルゴリズムと計算量

答え: B · 品物を分割できる分数ナップサック問題

これが答えになる理由

品物を分割できる場合は、比率の最もよいものから選ぶのが最適です。0/1 ナップサックでは比率の高い品物がよりよい組み合わせを妨げることがあるので、動的計画法が必要です。

答え

B · 品物を分割できる分数ナップサック問題
3.データ構造

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

これが答えになる理由

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

答え

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

答え: B · 使用中のスロットが長く連なる一次クラスタリング

これが答えになる理由

線形探査法は 1 ずつ進むので、使用中の連なりが大きくなって合体します。ダブルハッシュ法は 2 つ目のハッシュを刻み幅に使うので、異なるキーは異なる系列を探査します。

答え

B · 使用中のスロットが長く連なる一次クラスタリング
5.グラフ理論

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

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

次数

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

奇数次数の頂点

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

答え

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

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

6.グラフ理論

答え: W = 53

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

クラスカル法

EF (2): 取る
DF (4): 取る
CE (6): 取る
GC (10): 取る
GD (11): 飛ばす（閉路ができる）
AB (13): 取る
GE (14): 飛ばす（閉路ができる）
GB (18): 取る

重みの合計

W = 2 + 4 + 6 + 10 + 13 + 18 = 53

答え

W = 53

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