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

Що містить вказівник next останнього вузла однозв'язного списку?

1. ANull (жодного вузла)
2. BКількість вузлів у списку
3. CАдресу першого вузла
4. DАдресу попереднього вузла

Що робить геш-функція в геш-таблиці?

1. AРахує, скільки ключів збережено
2. BВідображає ключ в індекс у таблиці
3. CШифрує значення в таблиці
4. DСортує ключі в таблиці

Що таке орієнтований граф?

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

Чому обхід масиву на практиці часто значно швидший, ніж обхід зв'язного списку такої самої довжини?

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

AVL-дерева та червоно-чорні дерева гарантують:

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

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

1. AO(log V)
2. BO(1)
3. CO(E)
4. DO(V)

Який час роботи пошуку в ширину (BFS) у графі з V вершинами, що зберігається як матриця суміжності?

1. AO(V + E)
2. BO(E log V)
3. CO(V²)
4. DO(V)

Дерево відрізків (segment tree) зазвичай використовують для:

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