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

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

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

Що зберігається для кожної вершини в поданні графа списками суміжності?

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

Скільки ребер має дерево з n вузлами?

1. An + 1
2. B2n
3. Cn − 1
4. Dn

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

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

Яку структуру даних використовує виконувана програма, щоб відстежувати активні виклики функцій та їхні локальні змінні?

1. AГеш-таблицю функцій
2. BБінарне дерево пошуку фреймів
3. CСтек викликів
4. DЧергу пам'яті купи

Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?

1. AO(L), незалежно від кількості збережених слів
2. BO(log n), де n — кількість слів
3. CO(n), де n — кількість слів
4. DO(L × n)

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

1. AВін не використовує додаткової пам'яті
2. BОчікуваний пошук за O(log n) завдяки кільком рівням вказівників уперед
3. CВін зберігає ключі без упорядкування
4. DГарантований пошук за O(1), бо кожен вузол зберігає вказівник на кожен інший вузол

Яка вартість однієї операції find у найгіршому випадку в структурі union-find з n елементами без об'єднання за рангом і стиснення шляхів?

1. AO(n)
2. BO(1)
3. CO(α(n))
4. DO(log n)