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

Що визначає бінарне дерево?

1. AКожен вузол має рівно двох дітей
2. BКожен вузол зберігає двійкове число
3. CКожен вузол має щонайбільше двох дітей
4. DДерево має рівно два рівні

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

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

Яка головна відмінність між статичним і динамічним масивом?

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

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

1. A40
2. B20
3. C50
4. D70

Яка вартість вставлення елемента в середину масиву з n елементів?

1. AO(log n) через бінарний пошук
2. BO(1), бо індекс відомий
3. CO(n), бо наступні елементи доводиться зсувати
4. DO(n²), бо кожен елемент переміщується n разів

Чергу реалізовано двома стеками: push у стек «in» і pop зі стека «out», який поповнюють із «in», коли він порожній. Яка амортизована вартість однієї операції?

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

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

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

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

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