Яка умова збалансованості AVL?

У кожному вузлі висота(ліворуч) − висота(праворуч) ∈ {−1, 0, 1}. Дерево також задовольняє інваріант порядку BST.

Що таке коефіцієнт заповнення хеш-таблиці та навіщо змінювати її розмір?

α = n/m: n записів і m кошиків або комірок. Перевищення порога реалізації може спричинити збільшення та повторне хешування; 0,75 не є універсальним порогом.

Який інваріант порядку визначає двійкове дерево пошуку (BST) із різними ключами?

У кожному вузлі всі ключі лівого піддерева менші за його ключ, а правого — більші. Правило застосовується рекурсивно.

Як пошук, вставлення та видалення в BST залежать від висоти h?

Вони займають O(h). Збалансоване дерево має h = O(log n), ланцюжок — h = O(n). Очікуване O(log n) потребує припущень, наприклад випадкового порядку вставлення.

Скільки коштує побудова купи знизу вгору з n елементів?

O(n). Більшість вузлів близько до листків і потребують небагато просіювання вниз; сума роботи за висотами вузлів лінійна.

Скільки коштують вставлення, видалення кореня та перегляд кореня двійкової купи?

Відповідно O(log n), O(log n) та O(1), якщо не потрібно змінювати розмір масиву. Така зміна може коштувати O(n).

Порівняйте вставлення на початку й доступ за індексом в однозв'язному списку та динамічному масиві.

Список: вставлення на початку O(1), доступ за індексом O(n). Масив: вставлення на початку O(n), доступ за індексом O(1); вставлення спереду зсуває елементи.

Як метод ланцюжків розв'язує колізії хешування?

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

Який порядок доступу в черзі та типові витрати на її операції?

FIFO: додавання в кінець, вилучення з початку. Обидві операції займають O(1) із посиланнями на початок/кінець або в кільцевому буфері сталої місткості; зсув масиву робить вилучення O(n).

Що таке trie і коли пошук ключа з L символів займає O(L)?

Префіксне дерево зберігає ключі вздовж символьних шляхів із позначками повних ключів. Пошук займає O(L), якщо кожен перехід за наступним символом коштує O(1).

Які відповіді дає фільтр Блума, що допускає лише вставлення?

Негативна відповідь означає, що елемент не вставляли; позитивна — що могли вставити. Хеші встановлюють біти в масиві: хибнопозитивні відповіді можливі, хибнонегативні за неушкодженого стану — ні.

Які очікувані й найгірші витрати на операції в хеш-таблиці з ланцюжками?

За обмеженого заповнення, доброго розподілу хешів і сталої вартості операцій із ключами пошук/видалення мають очікувану вартість O(1). Вставлення з геометричним зростанням має очікувану амортизовану вартість O(1). Ланцюжок із n ключів у колізії може дати O(n).

Чому двозв'язний список може видалити заданий вузол за O(1)?

Посилання на попередній і наступний вузли дають змогу безпосередньо з'єднати сусідів. За потреби оновлюють початок і кінець; шукати попередника не потрібно.

Які правила кольорів підтримують баланс червоно-чорного BST?

Вузли червоні або чорні; корінь і листки NIL чорні. Червоні вузли не мають червоних дітей. Усі шляхи від вузла до листка NIL серед його нащадків містять однакову кількість чорних вузлів. Це обмежує висоту величиною O(log n).

Яка амортизована вартість union/find зі стисненням шляхів та об'єднанням за рангом?

O(α(n)) на операцію, де α — обернена функція Аккермана, n — кількість елементів. Ініціалізація коштує O(n); оцінка стосується послідовності, а не сталого найгіршого часу кожного виклику.

Які порядки прямого, симетричного та зворотного обходів двійкового дерева?

Прямий: вузол → ліворуч → праворуч. Симетричний: ліворуч → вузол → праворуч. Зворотний: ліворуч → праворуч → вузол.

Чим відрізняються лінійне та квадратичне зондування у відкритій адресації?

Записи залишаються в масиві. За розміру m і початкового індексу h перевіряють відповідно (h+i) mod m та (h+c₁i+c₂i²) mod m. Квадратичне зондування потребує належних параметрів.

Як обхід за рівнями відвідує двійкове дерево?

Черга FIFO дозволяє обробляти один рівень глибини за раз. Додавання лівої дитини перед правою забезпечує порядок зліва направо.

Що означає f(n) ∈ O(g(n)) для невід'ємних функцій f і g?

Існують сталі c > 0 і n₀ ≥ 0, такі що f(n) ≤ c·g(n) для всіх n ≥ n₀.

Що дає симетричний обхід BST із різними ключами?

Усі ключі в строго зростаючому порядку; n вузлів відвідуються за O(n).

Де розміщені батько й діти вузла i в масиві купи довжини n з індексацією від нуля?

Батько: ⌊(i−1)/2⌋ для i>0. Діти: 2i+1 та 2i+2, лише якщо ці індекси менші за n. Індекс 0 не має батька.

Чим відрізняються O, Ω і Θ?

Це відповідно асимптотична верхня, нижня та точна за порядком оцінка. Вони описують задану функцію витрат; O саме по собі не означає найгірший випадок.

Що роблять find та union у структурі неперетинних множин?

find(x) повертає представника множини x. union(x,y) об'єднує їхні множини, якщо вони різні; якщо вже збігаються, розбиття не змінюється.

Як виправити ліво-правий дисбаланс після вставлення в AVL?

Спочатку обернути ліву дитину ліворуч, потім незбалансований вузол праворуч.

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

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

Які властивості повинна мати хеш-функція для пошуку в таблиці?

Вона має бути детермінованою й добре розподіляти очікувані ключі. Хешування ключа фіксованого розміру може займати O(1); нового рядка з L символів — зазвичай O(L).

Чим відрізняються стиснення шляхів, об'єднання за рангом і за розміром?

Стиснення перенаправляє відвідані вузли до кореня. За рангом корінь меншого рангу приєднують під більший; за розміром меншу множину під більшу. Ранг не обов'язково дорівнює поточній висоті.

Як черга в кільцевому масиві уникає зсувів після вилучення?

Індекси початку та кінця циклічно змінюються за модулем місткості. Вилучення просуває початковий індекс, дозволяючи повторно використовувати вільні комірки без переміщення інших елементів.

Чому доступ за індексом у масиві фіксованого розміру займає O(1)?

Комірки однакового розміру розміщені послідовно: адреса(i) = база + i·розмір_комірки. Припускається сталий час обчислення адреси.

Яка амортизована вартість додавання в кінець динамічного масиву за подвоєння місткості?

O(1) на додавання. Зміна розміру може коштувати O(n), але n додавань до початково порожнього масиву сумарно коштують O(n).

Упорядкуйте темпи зростання від найповільнішого до найшвидшого при n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.

Асимптотично: 1 < log n < n < n log n < n² < 2ⁿ < n!.

Як працює стек і коли його операції займають O(1)?

LIFO: останній доданий елемент вилучається першим. На початку зв'язного списку додавання, вилучення й перегляд вершини займають O(1); зміна розміру масиву може зробити одне додавання O(n).

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

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

Level: basic
Languages: uk → uk
Cards: 32
Markdown: Структури даних, аналіз складності (Big-O) та фундаментальні алгоритми (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
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).