Робочий аркуш «Структури даних» з відповідями

Геш-таблиця (hash table) зберігає дані у вигляді:

1. AРядка фіксованої довжини
2. BЛише відсортованого списку
3. CДерева з упорядкованими ключами
4. DПар ключ–значення, розташування яких визначає геш-функція

Що таке властивість макс-купи?

1. AУсі листки містять максимальний ключ
2. BКлючі відсортовано зліва направо
3. CКлюч кожного батька більший або дорівнює ключам його дітей
4. DКлюч кожної лівої дитини більший або дорівнює ключу її правого брата чи сестри

Яка структура даних працює за принципом «останнім прийшов — першим вийшов» (LIFO)?

1. AЗв'язний список
2. BЧерга
3. CГеш-таблиця
4. DСтек

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

1. A1
2. Bn (дерево перетворюється на зв'язний список)
3. C√n
4. Dlog₂ n

Вузол бінарного дерева пошуку має праве піддерево. Де розташований його наступник у симетричному порядку (in-order successor)?

1. AЗавжди його батько
2. BКрайній правий вузол його лівого піддерева
3. CЗавжди його права дитина
4. DКрайній лівий вузол його правого піддерева

Префіксне дерево (trie) особливо ефективне для:

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

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

1. AВідсортований масив усіх n значень
2. BМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
3. CМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення
4. DЧерга FIFO з останніх k значень

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

1. AГеш-таблиця всіх елементів
2. BЧерга, що містить кожну пару елементів
3. CСтек, що зберігає елементи, які чекають на свою відповідь
4. DБінарне дерево пошуку, перебудоване для кожного елемента