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

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

Почему бинарный поиск не даёт времени O(log n) на односвязном списке?

  1. AСвязные списки нельзя сортировать
  2. BЧтобы добраться до среднего элемента, нужно O(n) шагов, поскольку нет прямого доступа по индексу
  3. CБинарному поиску нужно как минимум вдвое больше памяти
  4. DСравнения узлов связного списка медленнее
3.Структуры данныхСредняя

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

  1. AВ кучах никогда не бывает больше 100 элементов
  2. BЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
  3. CВсе ключи в куче равны
  4. DМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
4.Структуры данныхСложная

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

  1. AЧтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем
  2. BЧтобы гарантировать, что никакие два ключа никогда не столкнутся, какие бы ключи ни присылал атакующий
  3. CЧтобы не нужно было увеличивать таблицу
  4. DЧтобы хеш-таблица была отсортирована
5.Теория графовСредняя

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

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

Алгоритм Краскала строит минимальное остовное дерево. Нажмите на ребро, которое он добавляет под номером 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.Алгоритмы и сложность

Ответ: C · Алгоритм Дейкстры

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

Алгоритм Дейкстры работает с неотрицательными весами; алгоритм Беллмана–Форда допускает отрицательные веса; алгоритм Краскала строит минимальные остовные деревья.

Ответ

C · Алгоритм Дейкстры
2.Алгоритмы и сложность

Ответ: B · Чтобы добраться до среднего элемента, нужно O(n) шагов, поскольку нет прямого доступа по индексу

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

Бинарному поиску нужен доступ к середине за O(1); в связном списке путь туда стоит линейного времени, поэтому итог O(n).

Ответ

B · Чтобы добраться до среднего элемента, нужно O(n) шагов, поскольку нет прямого доступа по индексу
3.Структуры данных

Ответ: B · Это полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов

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

Полнота означает отсутствие пропусков, поэтому потомки индекса i всегда находятся в 2i + 1 и 2i + 2.

Ответ

B · Это полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
4.Структуры данных

Ответ: A · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем

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

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

Ответ

A · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем
5.Теория графов

Ответ: k = 5

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

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

12 − 1 = 11

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

k = 16 − 11 = 5

Ответ

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

Ответ: ребро BE

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

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

1. DE (2)
2. CE (5)
3. BE (6)
4. AC (13)

номер ребра 3

BE

Ответ

ребро BE

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