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

Яка визначальна риса множини як абстрактного типу даних?

1. AВона зберігає пари ключ–значення
2. BВона дозволяє доступ лише з одного кінця
3. CВона зберігає елементи без дублікатів
4. DВона зберігає елементи у відсортованому порядку

Яка структура даних найкраще підходить для функції «скасувати» (undo) у текстовому редакторі?

1. AГеш-множина
2. BЧерга
3. CСтек
4. DГраф

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

1. AВидалення головного елемента
2. BЧитання першого елемента
3. CВставлення на початок
4. DДоступ до елемента з індексом i

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

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

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

1. AВ індексі ⌊i / 2⌋ + 1
2. BВ індексі 2i + 1
3. CВ індексі i − 1
4. DВ індексі ⌊(i − 1) / 2⌋

Скільки вузлів має ідеальне бінарне дерево висоти h, якщо висоту рахують у ребрах?

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

Що робить розширюване дерево (splay tree) після кожного звертання?

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

Яку проблему лінійного зондування переважно зменшує подвійне гешування?

1. AПервинну кластеризацію, коли утворюються довгі серії зайнятих комірок
2. BПотребу зберігати ключі в таблиці
3. CПотребу в геш-функції
4. DВартість O(n) читання значення ключа