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

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

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

  1. AБлизько √n
  2. BБлизько log₂ n
  3. CБлизько n
  4. DБлизько n / 2
2.Алгоритми та складністьСкладна

Яке твердження про вибір k-го найменшого елемента невідсортованого масиву правильне?

  1. AВибір можливий лише за O(n²)
  2. BQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
  3. CQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента
  4. DВибір завжди потребує Ω(n log n), бо вимагає сортування
3.Структури данихСередня

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який прямий обхід (preorder)?

  1. A1 2 3 4 5
  2. B4 5 2 3 1
  3. C1 2 4 5 3
  4. D4 2 5 1 3
4.Структури данихСкладна

У циклічному буфері front == rear може означати як порожній, так і заповнений буфер. Який поширений спосіб їх розрізнити?

  1. AРобити розмір буфера степенем двійки
  2. BЗберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
  3. CЗберігати front і rear в одній змінній
  4. DЗавжди очищати буфер щоразу, коли front дорівнює rear, тож стан — порожній
5.Теорія графівСередня

Дерево має 3 вершин степеня 5, 3 вершин степеня 2, а всі його інші вершини — листки (степінь 1). Скільки листків L воно має?

3 × deg 53 × deg 2
L =
6.Теорія графівСкладна
95121115454865ABCDEFG

Алгоритм Дейкстри працює від A. Клікніть вершину, яку фіксують (роблять остаточною) у раунді 6; сама A — це раунд 1.

початок: Aраунд 6
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

3Розчини

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

Відповідь: B · Близько log₂ n

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

Ділення навпіл від n до 1 потребує близько log₂ n рівнів, і кожен рівень виконує O(n) роботи злиття, що дає O(n log n).

Відповідь

B · Близько log₂ n
2.Алгоритми та складність

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

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

Очікувана робота quickselect із випадковими опорними елементами — n + n/2 + n/4 + ... = O(n); вибір опорного елемента як медіани медіан робить найгірший випадок лінійним.

Відповідь

B · Quickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
3.Структури даних

Відповідь: C · 1 2 4 5 3

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

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

Відповідь

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

Відповідь: B · Зберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною

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

З лічильником порожній буфер означає count = 0, а заповнений — count = capacity; з однією порожньою коміркою заповненість визначають як (rear + 1) mod n == front.

Відповідь

B · Зберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
5.Теорія графів

Відповідь: L = 11

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

Лема про рукостискання для дерева

L + 21 = 2(L + 6) − 2
L = 11

Відповідь

L = 11

Скорочення: L = 2 + Σ (d − 2) за вершинами зі степенем d ≥ 3.

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

Відповідь: D

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

Алгоритм Дейкстри раунд за раундом

1. A (0): B: 9, C: 5
2. C (5): E: 16, G: 13
3. B (9)
4. G (13): D: 19
5. E (16): F: 21
6. D (19)
7. F (21)

раунд 6

D

Відповідь

D

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