# Структури даних, аналіз складності (Big-O) та фундаментальні алгоритми

> Повторення на рівні бакалаврату, що потребує основ програмування: 32 картки про масиви, списки, хешування, дерева, купи, trie, Union–Find, фільтри Блума та складність.

- **Canonical URL:** https://flashcards.world/flashcards/sets/7f77d34a-9acc-409a-af3d-6eed2d969edf/
- **Markdown URL:** https://flashcards.world/flashcards/sets/7f77d34a-9acc-409a-af3d-6eed2d969edf.md
- **Level:** basic
- **Languages:** uk → uk
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | Яка умова збалансованості AVL? | У кожному вузлі висота(ліворуч) − висота(праворуч) ∈ {−1, 0, 1}. Дерево також задовольняє інваріант порядку BST. |  |  |
| 2 | Що таке коефіцієнт заповнення хеш-таблиці та навіщо змінювати її розмір? | α = n/m: n записів і m кошиків або комірок. Перевищення порога реалізації може спричинити збільшення та повторне хешування; 0,75 не є універсальним порогом. |  |  |
| 3 | Який інваріант порядку визначає двійкове дерево пошуку (BST) із різними ключами? | У кожному вузлі всі ключі лівого піддерева менші за його ключ, а правого — більші. Правило застосовується рекурсивно. |  |  |
| 4 | Як пошук, вставлення та видалення в BST залежать від висоти h? | Вони займають O(h). Збалансоване дерево має h = O(log n), ланцюжок — h = O(n). Очікуване O(log n) потребує припущень, наприклад випадкового порядку вставлення. |  |  |
| 5 | Скільки коштує побудова купи знизу вгору з n елементів? | O(n). Більшість вузлів близько до листків і потребують небагато просіювання вниз; сума роботи за висотами вузлів лінійна. |  |  |
| 6 | Скільки коштують вставлення, видалення кореня та перегляд кореня двійкової купи? | Відповідно O(log n), O(log n) та O(1), якщо не потрібно змінювати розмір масиву. Така зміна може коштувати O(n). |  |  |
| 7 | Порівняйте вставлення на початку й доступ за індексом в однозв'язному списку та динамічному масиві. | Список: вставлення на початку O(1), доступ за індексом O(n). Масив: вставлення на початку O(n), доступ за індексом O(1); вставлення спереду зсуває елементи. |  |  |
| 8 | Як метод ланцюжків розв'язує колізії хешування? | Кожен кошик містить колекцію записів із цим індексом, часто зв'язний список. Різні ключі в одному кошику залишаються окремими записами. |  |  |
| 9 | Який порядок доступу в черзі та типові витрати на її операції? | FIFO: додавання в кінець, вилучення з початку. Обидві операції займають O(1) із посиланнями на початок/кінець або в кільцевому буфері сталої місткості; зсув масиву робить вилучення O(n). |  |  |
| 10 | Що таке trie і коли пошук ключа з L символів займає O(L)? | Префіксне дерево зберігає ключі вздовж символьних шляхів із позначками повних ключів. Пошук займає O(L), якщо кожен перехід за наступним символом коштує O(1). |  |  |
| 11 | Які відповіді дає фільтр Блума, що допускає лише вставлення? | Негативна відповідь означає, що елемент не вставляли; позитивна — що могли вставити. Хеші встановлюють біти в масиві: хибнопозитивні відповіді можливі, хибнонегативні за неушкодженого стану — ні. |  |  |
| 12 | Які очікувані й найгірші витрати на операції в хеш-таблиці з ланцюжками? | За обмеженого заповнення, доброго розподілу хешів і сталої вартості операцій із ключами пошук/видалення мають очікувану вартість O(1). Вставлення з геометричним зростанням має очікувану амортизовану вартість O(1). Ланцюжок із n ключів у колізії може дати O(n). |  |  |
| 13 | Чому двозв'язний список може видалити заданий вузол за O(1)? | Посилання на попередній і наступний вузли дають змогу безпосередньо з'єднати сусідів. За потреби оновлюють початок і кінець; шукати попередника не потрібно. |  |  |
| 14 | Які правила кольорів підтримують баланс червоно-чорного BST? | Вузли червоні або чорні; корінь і листки NIL чорні. Червоні вузли не мають червоних дітей. Усі шляхи від вузла до листка NIL серед його нащадків містять однакову кількість чорних вузлів. Це обмежує висоту величиною O(log n). |  |  |
| 15 | Яка амортизована вартість union/find зі стисненням шляхів та об'єднанням за рангом? | O(α(n)) на операцію, де α — обернена функція Аккермана, n — кількість елементів. Ініціалізація коштує O(n); оцінка стосується послідовності, а не сталого найгіршого часу кожного виклику. |  |  |
| 16 | Які порядки прямого, симетричного та зворотного обходів двійкового дерева? | Прямий: вузол → ліворуч → праворуч. Симетричний: ліворуч → вузол → праворуч. Зворотний: ліворуч → праворуч → вузол. |  |  |
| 17 | Чим відрізняються лінійне та квадратичне зондування у відкритій адресації? | Записи залишаються в масиві. За розміру m і початкового індексу h перевіряють відповідно (h+i) mod m та (h+c₁i+c₂i²) mod m. Квадратичне зондування потребує належних параметрів. |  |  |
| 18 | Як обхід за рівнями відвідує двійкове дерево? | Черга FIFO дозволяє обробляти один рівень глибини за раз. Додавання лівої дитини перед правою забезпечує порядок зліва направо. |  |  |
| 19 | Що означає f(n) ∈ O(g(n)) для невід'ємних функцій f і g? | Існують сталі c > 0 і n₀ ≥ 0, такі що f(n) ≤ c·g(n) для всіх n ≥ n₀. |  |  |
| 20 | Що дає симетричний обхід BST із різними ключами? | Усі ключі в строго зростаючому порядку; n вузлів відвідуються за O(n). |  |  |
| 21 | Де розміщені батько й діти вузла i в масиві купи довжини n з індексацією від нуля? | Батько: ⌊(i−1)/2⌋ для i>0. Діти: 2i+1 та 2i+2, лише якщо ці індекси менші за n. Індекс 0 не має батька. |  |  |
| 22 | Чим відрізняються O, Ω і Θ? | Це відповідно асимптотична верхня, нижня та точна за порядком оцінка. Вони описують задану функцію витрат; O саме по собі не означає найгірший випадок. |  |  |
| 23 | Що роблять find та union у структурі неперетинних множин? | find(x) повертає представника множини x. union(x,y) об'єднує їхні множини, якщо вони різні; якщо вже збігаються, розбиття не змінюється. |  |  |
| 24 | Як виправити ліво-правий дисбаланс після вставлення в AVL? | Спочатку обернути ліву дитину ліворуч, потім незбалансований вузол праворуч. |  |  |
| 25 | Які дві властивості визначають мінімальну двійкову купу? | Усі рівні заповнені, крім, можливо, останнього, який заповнюється зліва. Ключ батька не більший за ключі дітей. Отже, корінь містить мінімум. |  |  |
| 26 | Які властивості повинна мати хеш-функція для пошуку в таблиці? | Вона має бути детермінованою й добре розподіляти очікувані ключі. Хешування ключа фіксованого розміру може займати O(1); нового рядка з L символів — зазвичай O(L). |  |  |
| 27 | Чим відрізняються стиснення шляхів, об'єднання за рангом і за розміром? | Стиснення перенаправляє відвідані вузли до кореня. За рангом корінь меншого рангу приєднують під більший; за розміром меншу множину під більшу. Ранг не обов'язково дорівнює поточній висоті. |  |  |
| 28 | Як черга в кільцевому масиві уникає зсувів після вилучення? | Індекси початку та кінця циклічно змінюються за модулем місткості. Вилучення просуває початковий індекс, дозволяючи повторно використовувати вільні комірки без переміщення інших елементів. |  |  |
| 29 | Чому доступ за індексом у масиві фіксованого розміру займає O(1)? | Комірки однакового розміру розміщені послідовно: адреса(i) = база + i·розмір_комірки. Припускається сталий час обчислення адреси. |  |  |
| 30 | Яка амортизована вартість додавання в кінець динамічного масиву за подвоєння місткості? | O(1) на додавання. Зміна розміру може коштувати O(n), але n додавань до початково порожнього масиву сумарно коштують O(n). |  |  |
| 31 | Упорядкуйте темпи зростання від найповільнішого до найшвидшого при n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n. | Асимптотично: 1 < log n < n < n log n < n² < 2ⁿ < n!. |  |  |
| 32 | Як працює стек і коли його операції займають O(1)? | LIFO: останній доданий елемент вилучається першим. На початку зв'язного списку додавання, вилучення й перегляд вершини займають O(1); зміна розміру масиву може зробити одне додавання O(n). |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/7f77d34a-9acc-409a-af3d-6eed2d969edf/).