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

Що таке цикл у графі?

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

У бінарному дереві пошуку значення в лівому піддереві вузла:

1. AБільші за значення вузла
2. BМенші за значення вузла
3. CРозташовані у випадковому порядку
4. DДорівнюють значенню вузла

Глибина вузла в дереві — це:

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

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

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

Як вставляють новий елемент у бінарну купу?

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

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

1. AЗбалансоване бінарне дерево пошуку
2. BНевідсортований зв'язний список
3. CСтек
4. DГеш-таблиця

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

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

Для чого використовують структуру union-find в алгоритмі Краскала для мінімального кістякового дерева?

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