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

公式集、全トピックの解法の要点、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 の配列
2.アルゴリズムと計算量むずかしい

クック－レビンの定理は何を確立しましたか？

  1. A停止問題が決定不能であること
  2. Bブール充足可能性問題（SAT）が NP 完全であること
  3. Cすべての NP 問題が指数時間で解けること
  4. DP が NP と等しくないこと
3.データ構造ふつう

衝突したキーを同じバケット内のリストに格納する衝突解決法はどれですか。

  1. A二次探査法（Quadratic probing）
  2. Bチェイン法（Separate chaining）
  3. Cダブルハッシュ法（Double hashing）
  4. D線形探査法（Linear probing）
4.データ構造むずかしい

スプレー木は各アクセスの後に何をしますか。

  1. Aアクセスしたノードを根まで回転させて持ち上げる
  2. B探索経路上のノードの色を塗り替える
  3. Cアクセスしたノードを葉に移す
  4. D木全体を平衡な形に作り直す
5.グラフ理論ふつう

完全グラフ K4 には、異なるハミルトン閉路が何個Hありますか？ 始点や向きだけが異なる閉路は同じものとして数えます。

K4
H =
6.グラフ理論むずかしい
20159267115ABCDEF

クラスカル法は最小全域木をつくります。それが 2 番目に加える辺をクリックしてください。飛ばされた辺は数えません。

k = 2
  1. 1辺 AB
  2. 2辺 AC
  3. 3辺 BC
  4. 4辺 BD
  5. 5辺 CE
  6. 6辺 DE
  7. 7辺 EF
  8. 8辺 BE

3溶液

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

答え: B · すでにソートされている配列

これが答えになる理由

ソート済みの入力ではピボットが常に最小値になるので、一方は空、もう一方は n − 1 個の要素となり、O(n²) になります。

答え

B · すでにソートされている配列
2.アルゴリズムと計算量

答え: B · ブール充足可能性問題（SAT）が NP 完全であること

これが答えになる理由

クックとレビンは独立に、NP のすべての問題が多項式時間で SAT に帰着することを示したので、SAT は最初に知られた NP 完全問題となりました。

答え

B · ブール充足可能性問題（SAT）が NP 完全であること
3.データ構造

答え: B · チェイン法（Separate chaining）

これが答えになる理由

チェイン法はバケットごとに連結リスト（または別の構造）を持ち、オープンアドレス法はテーブル内で別の空きスロットを探します。

答え

B · チェイン法（Separate chaining）
4.データ構造

答え: A · アクセスしたノードを根まで回転させて持ち上げる

これが答えになる理由

スプレー操作は回転によってアクセスしたノードを根に移します。1 回の操作に O(n) かかることもありますが、ならしコストは O(log n) です。

答え

A · アクセスしたノードを根まで回転させて持ち上げる
5.グラフ理論

答え: H = 3

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

数える

H = (4 − 1)!/2 = 6/2 = 3

答え

H = 3
6.グラフ理論

答え: 辺 BE

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

クラスカル法

1. BD (2)
2. BE (5)
3. CE (6)
4. EF (11)
5. AC (15)

辺の番号 2

BE

答え

辺 BE

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