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

公式集、全トピックの解法の要点、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Ω(n²)
  2. BΩ(log n)
  3. CΩ(n)
  4. DΩ(n log n)
2.アルゴリズムと計算量むずかしい

ハッシュテーブルの平均探索時間が O(1) なのに、最悪の場合は O(n) になるのはなぜですか？

  1. Aキーを先にソートする必要があるから
  2. B多くのキーが同じバケットで衝突（collision）する可能性があるから
  3. Cハッシュ関数が遅いから
  4. D配列のアクセスが O(n) だから
3.データ構造ふつう

キーをソート済みの順序で挿入した場合、n 個のノードを持つ二分探索木の最悪の高さはいくつですか。

  1. An（連結リストのようになる）
  2. Blog₂ n
  3. C√n
  4. D1
4.データ構造むずかしい

ヒープソートについて正しい記述はどれですか。

  1. A追加の記憶領域として二分探索木を必要とするので、O(n) の追加メモリを使う
  2. B最悪 O(n log n) 時間でその場でソートするが、安定ではない
  3. C安定で、O(n) の追加メモリを必要とする
  4. Dどの入力に対しても O(n) 時間で動作する
5.グラフ理論ふつう
ABCDEオイラー閉路オイラー路あり、閉路なしどちらでもない

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

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

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

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

3溶液

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

答え: D · Ω(n log n)

これが答えになる理由

どの比較ソートも、最悪の場合に少なくとも log₂(n!) ≈ n log n 回の比較が必要です。計数ソートは比較を行わないため、この下界を下回ることができます。

答え

D · Ω(n log n)
2.アルゴリズムと計算量

答え: B · 多くのキーが同じバケットで衝突（collision）する可能性があるから

これが答えになる理由

良いハッシュ関数と負荷率（load factor）であれば、バケットは平均して短く保たれます。悪意のある入力や質の悪いハッシュでは、すべてのキーが一つのバケットに入ることがあります。

答え

B · 多くのキーが同じバケットで衝突（collision）する可能性があるから
3.データ構造

答え: A · n（連結リストのようになる）

これが答えになる理由

ソート済みの挿入では高さ n の退化した木ができ、探索が O(n) になります。平衡木はこれを防ぎます。

答え

A · n（連結リストのようになる）
4.データ構造

答え: B · 最悪 O(n log n) 時間でその場でソートするが、安定ではない

これが答えになる理由

ヒープソートは最大ヒープを構築し、同じ配列内で最大値を n 回取り出します。遠く離れた位置どうしの交換によって、等しいキーの順序が入れ替わることがあります。

答え

B · 最悪 O(n log n) 時間でその場でソートするが、安定ではない
5.グラフ理論

答え: オイラー閉路

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

次数

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

奇数次数の頂点

0
オイラー閉路

答え

オイラー閉路
6.グラフ理論

答え: 辺 BD

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

クラスカル法

1. AB (1)
2. AC (4)
3. BD (11)
4. BE (13)

辺の番号 3

BD

答え

辺 BD

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