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

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

1. AГраф
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Вона симетрична відносно головної діагоналі
4. DКожен рядок містить рівно одну 1

Кільцевий буфер (ring buffer) зазвичай використовують для реалізації:

1. AОбходу графа
2. BЧерги фіксованого розміру
3. CГеш-функції
4. DБінарного дерева пошуку

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

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

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

1. AУсі записи розташовані у зв'язаних листках, що робить сканування діапазонів ефективним
2. BB+ дерева зберігають дані лише в корені
3. CB+ дерева використовують бінарні внутрішні вузли, що зменшує кількість зчитувань із диска
4. DB+ дерева не потребують збалансування

Який очікуваний час пошуку за простого рівномірного гешування в геш-таблиці з ланцюжками, n ключами та m кошиками?

1. AO(1 + α), де α = n / m
2. BO(log n)
3. CO(m)
4. DO(n)