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

Що таке степінь вершини в неорієнтованому графі?

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

В однозв'язному списку кожен вузол містить:

1. AДані та посилання на всі інші вузли
2. BДані та посилання на наступний вузол
3. CДані та індекс
4. DЛише дані

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

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

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

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

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

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

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

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

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

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

Яке твердження про пірамідальне сортування (heapsort) правильне?

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