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

Листы формул, ключевые шаги методов по каждой теме и тренировочные задачи (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Рекурсивные алгоритмы не справляются с массивами меньше 10 элементов
  3. CСортировка вставками имеет сложность O(n log n) в худшем случае
  4. DУ сортировки вставками малые накладные расходы, и она быстра на маленьких или почти отсортированных входах
2.Алгоритмы и сложностьСложная

Задача о рюкзаке 0/1, решаемая динамическим программированием, требует O(nW) времени. Почему это называют псевдополиномиальным временем?

  1. AW — число, поэтому время экспоненциально относительно количества битов, используемых для записи W
  2. BПотому что n всегда мало
  3. CПотому что алгоритм рандомизированный, и время его работы меняется для каждого входа
  4. DПотому что он работает только при W = 0
3.Структуры данныхСредняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков прямой обход (preorder)?

  1. A4 5 2 3 1
  2. B1 2 3 4 5
  3. C1 2 4 5 3
  4. D4 2 5 1 3
4.Структуры данныхСложная

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

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

Связный граф имеет 11 вершин и 21 рёбер. Сколько рёбер, k, нужно удалить, чтобы осталось остовное дерево?

|V| = 11|E| = 21
k =
6.Теория графовСложная
ABCDE

Сколько существует замкнутых маршрутов длины 2, начинающихся и заканчивающихся в B? Маршрут может повторять вершины и рёбра. Обозначим это число N.

M = матрица смежностиL = 2
N =

3Растворы

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

Ответ: D · У сортировки вставками малые накладные расходы, и она быстра на маленьких или почти отсортированных входах

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

При малых n простой цикл сортировки вставками выигрывает у накладных расходов рекурсии быстрой сортировки или сортировки слиянием, хотя он O(n²).

Ответ

D · У сортировки вставками малые накладные расходы, и она быстра на маленьких или почти отсортированных входах
2.Алгоритмы и сложность

Ответ: A · W — число, поэтому время экспоненциально относительно количества битов, используемых для записи W

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

Время работы полиномиально относительно значения W, но экспоненциально относительно его длины (log W битов); задача о рюкзаке 0/1 является NP-полной.

Ответ

A · W — число, поэтому время экспоненциально относительно количества битов, используемых для записи W
3.Структуры данных

Ответ: C · 1 2 4 5 3

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

Прямой обход посещает 1, затем его левое поддерево (2, 4, 5), затем 3; остальные варианты — симметричный, обратный обход и обход по уровням.

Ответ

C · 1 2 4 5 3
4.Структуры данных

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

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

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

Ответ

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

Ответ: k = 11

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

Рёбра остовного дерева

11 − 1 = 10

Рёбра для удаления

k = 21 − 10 = 11

Ответ

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

Ответ: N = 3

Степени: степень вершины — это число рёбер, которые в ней сходятся. У каждого ребра два конца, поэтому степени в сумме дают удвоенное число рёбер: Σ deg(v) = 2|E| (лемма о рукопожатиях). Следовательно, число вершин нечётной степени чётно. У Kn имеется n(n − 1)/2 рёбер, у k-регулярного графа на n вершинах nk/2, а у дерева на n вершинах n − 1 ребро.

Матрица смежности

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

Общие соседи

(M²)BB = 1·1 + 0·0 + 0·0 + 1·1 + 1·1 = 3

Ответ

N = 3

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