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

Аркуші з формулами, ключові кроки методів для кожної теми та 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
Ейлер
цикл: усі степені парні; шлях: рівно 2 непарні степені
Гамільтонові цикли в 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Найкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
  2. BМінімальне кістякове дерево за O(E log V)
  3. CНайкоротші шляхи між усіма парами вершин за O(V³)
  4. DТопологічний порядок за O(V²)
2.Алгоритми та складністьСкладна

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

  1. AВибір опорного елемента випадково з рівномірним розподілом
  2. BЗастосування рекурсії лише до лівої частини
  3. CВибір завжди першого елемента
  4. DСортування вхідних даних перед запуском швидкого сортування
3.Структури данихСередня

Як знайти мінімальний ключ у бінарному дереві пошуку?

  1. AІти від кореня лівими дітьми, доки лівої дитини не буде
  2. BПодивитися лише на корінь
  3. CВідвідати кожен листок і порівняти їх
  4. DІти від кореня правими дітьми, доки правої дитини не буде
4.Структури данихСкладна

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

  1. AВоно стабільне й потребує O(n) додаткової пам'яті
  2. BВоно сортує на місці за час O(n log n) у найгіршому випадку, але не є стабільним
  3. CВоно працює за час O(n) на будь-яких вхідних даних
  4. DВоно потребує бінарного дерева пошуку як додаткового сховища, тож використовує O(n) додаткової пам'яті
5.Теорія графівСередня

Зв’язний граф має 14 вершин і 17 ребер. Скільки ребер k треба вилучити, щоб залишилося остовне дерево?

|V| = 14|E| = 17
k =
6.Теорія графівСкладна
1815517137129ABCDEF

Знайдіть загальну вагу W мінімального остовного дерева зваженого графа.

|V| = 6|E| = 8
W =

3Розчини

1.Алгоритми та складність

Відповідь: C · Найкоротші шляхи між усіма парами вершин за O(V³)

Чому це відповідь

Флойд–Воршелл — алгоритм динамічного програмування, що по черзі дозволяє кожну вершину як проміжну, витрачаючи O(V³) часу.

Відповідь

C · Найкоротші шляхи між усіма парами вершин за O(V³)
2.Алгоритми та складність

Відповідь: A · Вибір опорного елемента випадково з рівномірним розподілом

Чому це відповідь

З випадковим опорним елементом очікуваний час роботи становить O(n log n) для будь-яких вхідних даних; погані випадки все ще можливі, але дуже малоймовірні.

Відповідь

A · Вибір опорного елемента випадково з рівномірним розподілом
3.Структури даних

Відповідь: A · Іти від кореня лівими дітьми, доки лівої дитини не буде

Чому це відповідь

Крайній лівий вузол не має меншого ключа в дереві, тож він і є мінімумом; вартість пропорційна висоті.

Відповідь

A · Іти від кореня лівими дітьми, доки лівої дитини не буде
4.Структури даних

Відповідь: B · Воно сортує на місці за час O(n log n) у найгіршому випадку, але не є стабільним

Чому це відповідь

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

Відповідь

B · Воно сортує на місці за час O(n log n) у найгіршому випадку, але не є стабільним
5.Теорія графів

Відповідь: k = 4

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

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

14 − 1 = 13

Ребра для вилучення

k = 17 − 13 = 4

Відповідь

k = 4
6.Теорія графів

Відповідь: W = 48

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

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

BC (5): взяти
DF (7): взяти
BE (9): взяти
EF (12): взяти
CE (13): пропустити, замикає цикл
AC (15): взяти

Загальна вага

W = 5 + 7 + 9 + 12 + 15 = 48

Відповідь

W = 48

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