Алгоритмы и структуры данных: шпаргалка-пакет

Листы формул, ключевые шаги методов по каждой теме и тренировочные задачи (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
Эйлер
цикл: все степени чётные; путь: ровно две нечётные степени
Гамильтоновы циклы в Kn
(n − 1)!/2
Обновление в алгоритме Дейкстры
d(v) = min(d(v), d(u) + w(u, v))
Маршруты длины L
(Mᴸ)ij

Метод

  1. Запишите степень каждой вершины; сумма степеней равна удвоенному числу рёбер.
  2. В задачах об эйлеровых путях проверьте, что граф связный, и посчитайте вершины нечётной степени.
  3. Для деревьев используйте n − 1 ребро и лемму о рукопожатиях.
  4. В алгоритме Дейкстры ведите таблицу предварительных расстояний и на каждом шаге фиксируйте нефиксированную вершину с наименьшим расстоянием.
  5. Для минимального остовного дерева отсортируйте рёбра по весу и пропускайте каждое ребро, замыкающее цикл (Краскал), либо растите одно дерево из начальной вершины (Прим).

2Тренировочные задачи

1.Алгоритмы и сложностьСредняя

Какой алгоритм сортировки является устойчивым?

  1. AБыстрая сортировка (типичная версия на месте)
  2. BСортировка слиянием
  3. CПирамидальная сортировка
  4. DСортировка выбором (типичная версия)
2.Алгоритмы и сложностьСложная

Если взять оба конца каждого ребра максимального (по включению) паросочетания, получится вершинное покрытие. Насколько оно хорошее?

  1. AНе более чем вдвое больше минимального вершинного покрытия
  2. BНе более чем в log n раз больше минимума
  3. CВсегда минимальное вершинное покрытие
  4. DНеизвестного качества по сравнению с оптимумом
3.Структуры данныхСредняя

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

  1. AОба поддерева каждого узла содержат ровно одинаковое число узлов
  2. BКаждый узел окрашен в красный или чёрный цвет
  3. CВсе листья находятся ровно на одной глубине
  4. DВысоты левого и правого поддеревьев различаются не более чем на 1
4.Структуры данныхСложная

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

  1. AВысота не превышает 2 log2(n + 1)
  2. BВысота равна ровно log2 n
  3. CВысота не превышает log2 n + 1
  4. DВысота не превышает n / 2
5.Теория графовСредняя

У дерева 2 вершин степени 3, 3 вершин степени 4, 3 вершин степени 5, 4 вершин степени 2, а все остальные его вершины — листья (степень 1). Сколько у него листьев, L?

2 × deg 33 × deg 43 × deg 54 × deg 2
L =
6.Теория графовСложная
201815161162ABCDE

Найдите суммарный вес W минимального остовного дерева взвешенного графа.

|V| = 5|E| = 7
W =

3Растворы

1.Алгоритмы и сложность

Ответ: B · Сортировка слиянием

Почему это ответ

Сортировка слиянием устойчива, если при равных ключах во время слияния сначала берётся элемент из левой половины. Быстрая сортировка на месте, пирамидальная сортировка и сортировка выбором обычно неустойчивы.

Ответ

B · Сортировка слиянием
2.Алгоритмы и сложность

Ответ: A · Не более чем вдвое больше минимального вершинного покрытия

Почему это ответ

Рёбра паросочетания не имеют общих вершин, поэтому оптимуму нужна хотя бы одна вершина на ребро, а этот метод берёт две: это 2-приближение.

Ответ

A · Не более чем вдвое больше минимального вершинного покрытия
3.Структуры данных

Ответ: D · Высоты левого и правого поддеревьев различаются не более чем на 1

Почему это ответ

Показатель сбалансированности (высота левого − высота правого) должен быть −1, 0 или 1; повороты восстанавливают его после вставок и удалений.

Ответ

D · Высоты левого и правого поддеревьев различаются не более чем на 1
4.Структуры данных

Ответ: A · Высота не превышает 2 log2(n + 1)

Почему это ответ

На каждом пути одинаковое число чёрных узлов, а красные узлы не могут быть соседними, поэтому самый длинный путь не более чем вдвое длиннее самого короткого, что даёт высоту O(log n).

Ответ

A · Высота не превышает 2 log2(n + 1)
5.Теория графов

Ответ: L = 19

Эйлер, Гамильтон и деревья: связный граф имеет эйлеров цикл (каждое ребро один раз, с возвратом в начало), когда все вершины имеют чётную степень, и эйлеров путь, не являющийся циклом, когда ровно две вершины имеют нечётную степень; тогда путь идёт от одной нечётной вершины к другой. Гамильтонов цикл посещает каждую вершину один раз; в Kn их (n − 1)!/2. У дерева на n вершинах n − 1 ребро, а связный граф с m рёбрами сохраняет остовное дерево после удаления m − n + 1 рёбер.

Лемма о рукопожатиях для дерева

L + 41 = 2(L + 12) − 2
L = 19

Ответ

L = 19

Короткий путь: L = 2 + Σ (d − 2) по вершинам степени d ≥ 3.

6.Теория графов

Ответ: W = 37

Кратчайшие пути и остовные деревья: алгоритм Дейкстры фиксирует по одной вершине на шаге: нефиксированную вершину с наименьшим предварительным расстоянием. Её расстояние становится окончательным, а каждый сосед v получает d(v) = min(d(v), d(u) + w(u, v)). Алгоритм Краскала строит минимальное остовное дерево, беря рёбра от лёгких к тяжёлым и пропуская любое ребро, которое замкнуло бы цикл; алгоритм Прима растит одно дерево из начальной вершины, всегда добавляя самое лёгкое ребро, выходящее из него. В остовном дереве на n вершинах n − 1 ребро.

Алгоритм Краскала

BE (2): берём
DE (6): берём
CE (11): берём
BC (15): пропускаем, замыкает цикл
BD (16): пропускаем, замыкает цикл
AC (18): берём

Суммарный вес

W = 2 + 6 + 11 + 18 = 37

Ответ

W = 37

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