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

Листы формул, ключевые шаги методов по каждой теме и тренировочные задачи (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.Алгоритмы и сложностьСложная

Как соотносятся n! и 2ⁿ при больших n?

  1. An! есть O(n²)
  2. Bn! растёт быстрее 2ⁿ
  3. C2ⁿ растёт быстрее n!
  4. DОни растут с одинаковой скоростью
3.Структуры данныхСредняя

Приложению нужен быстрый поиск, а также вывод ключей в отсортированном порядке и запросы по диапазону. Какая структура подходит лучше всего?

  1. AСтек
  2. BНеотсортированный связный список
  3. CСбалансированное двоичное дерево поиска
  4. DХеш-таблица
4.Структуры данныхСложная

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

  1. AОтображение выбрасывает ошибку в момент изменения поля
  2. BПоиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
  3. CОтображение автоматически переносит ключ в новую корзину
  4. DНичего не меняется, потому что хеш ключа вычисляется только один раз при запуске программы
5.Теория графовСредняя

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

|V| = 7|E| = 15
k =
6.Теория графовСложная
58261214109912ABCDEFG

Алгоритм Дейкстры запускается из A. Нажмите на вершину, которая фиксируется (становится постоянной) на шаге 3; сама A фиксируется на шаге 1.

начало: Aшаг 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

3Растворы

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

Ответ: A · Оптимальное решение можно построить из оптимальных решений её подзадач

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

Оптимальная подструктура необходима, чтобы и жадные алгоритмы, и динамическое программирование давали правильные ответы.

Ответ

A · Оптимальное решение можно построить из оптимальных решений её подзадач
2.Алгоритмы и сложность

Ответ: B · n! растёт быстрее 2ⁿ

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

При n ≥ 4 n! превышает 2ⁿ, и отношение растёт неограниченно, потому что каждый новый множитель n! больше 2.

Ответ

B · n! растёт быстрее 2ⁿ
3.Структуры данных

Ответ: C · Сбалансированное двоичное дерево поиска

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

Сбалансированное BST даёт поиск за O(log n) и хранит ключи упорядоченными, поэтому симметричный обход и запросы по диапазону просты; хеш-таблица разбрасывает ключи.

Ответ

C · Сбалансированное двоичное дерево поиска
4.Структуры данных

Ответ: B · Поиск объекта может не удаться, потому что он лежит в корзине своего старого хеша

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

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

Ответ

B · Поиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
5.Теория графов

Ответ: k = 9

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

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

7 − 1 = 6

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

k = 15 − 6 = 9

Ответ

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

Ответ: C

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

Алгоритм Дейкстры по шагам

1. A (0): B: 5, C: 8
2. B (5): C: 7, D: 11, G: 14
3. C (7): E: 19
4. D (11): F: 21
5. G (14)
6. E (19)
7. F (21)

шаг 3

C

Ответ

C

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