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

Що таке листок у дереві?

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Стек

Як працює extract-min у бінарній мін-купі?

1. AШукають новий мінімум серед усіх листків
2. BВидаляють останній елемент масиву
3. CВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
4. DОстанній елемент переміщують у корінь і просіюють униз

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

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

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

1. A√n
2. B1
3. Clog₂ n
4. Dn (дерево перетворюється на зв'язний список)

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

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

Яка структура даних забезпечує кеш LRU (least recently used) з операціями get і put за O(1)?

1. AОдин відсортований масив
2. BГеш-мапа в поєднанні з двозв'язним списком
3. CЛише стек
4. DЛише бінарне дерево пошуку