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

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

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

Як називається операція стека, що додає елемент на вершину?

1. APush
2. BPeek
3. CEnqueue
4. DPop

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

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

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

1. A√n
2. B1
3. Clog₂ n
4. Dn (дерево перетворюється на зв'язний список)

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

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

Яка часова складність пошуку ключа в збалансованому бінарному дереві пошуку?

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

Як визначити, чи містить однозв'язний список цикл, використовуючи O(1) додаткової пам'яті?

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

Чому B-дерева використовують у базах даних і файлових системах?

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