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

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

Сколько памяти стека использует простая рекурсивная функция факториала fact(n) = n × fact(n − 1)?

  1. AO(log n)
  2. BO(n)
  3. CO(n²)
  4. DO(1)
2.Алгоритмы и сложностьСложная

Какое определение класса P верно?

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

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

  1. AОна работает за O(n) на любых входных данных
  2. BЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
  3. CОна устойчива и требует O(n) дополнительной памяти
  4. DОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
5.Теория графовСредняя
ABCDEFGЭйлеров циклЭйлеров путь, не циклни то, ни другое

Есть ли в связном графе эйлеров цикл, эйлеров путь, не являющийся циклом, или ни то ни другое? Нажмите на ваш ответ.

|V| = 7|E| = 10
  1. 1Эйлеров цикл
  2. 2Эйлеров путь, не цикл
  3. 3ни то, ни другое
6.Теория графовСложная
ABCDEF

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

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

3Растворы

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

Ответ: B · O(n)

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

Глубина рекурсии — n вызовов до первого возврата, и каждому вызову нужен кадр стека, поэтому используется O(n) памяти.

Ответ

B · O(n)
2.Алгоритмы и сложность

Ответ: C · Задачи распознавания, решаемые детерминированным алгоритмом за полиномиальное время

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

P содержит задачи распознавания с детерминированным полиномиальным алгоритмом, например проверку связности графа.

Ответ

C · Задачи распознавания, решаемые детерминированным алгоритмом за полиномиальное время
3.Структуры данных

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

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

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

Ответ

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

Ответ: D · Она сортирует на месте за O(n log n) в худшем случае, но не является устойчивой

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

Heapsort строит max-кучу и n раз извлекает максимум в том же массиве; обмены на большие расстояния могут менять порядок равных ключей.

Ответ

D · Она сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
5.Теория графов

Ответ: ни то, ни другое

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

Степени

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

Нечётные вершины

B, D, E, G → 4
ни то, ни другое

Ответ

ни то, ни другое
6.Теория графов

Ответ: N = 4

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

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

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

Общие соседи

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

Ответ

N = 4

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