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

Яку структуру зазвичай використовують для реалізації черги з пріоритетом?

1. AСтек
2. BНевпорядкований однозв'язний список
3. CРядок
4. DКупу

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

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

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

Який абстрактний тип даних використовує алгоритм Дейкстри, щоб обрати наступну вершину для обробки?

1. AМін-чергу з пріоритетом
2. BЧергу FIFO
3. CСтек
4. DМножину без упорядкування

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який прямий обхід (preorder)?

1. A1 2 3 4 5
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

1. AМаксимуму немає
2. B2
3. C0,5
4. D1

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

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

Чим radix-дерево (стиснене префіксне дерево) краще за звичайне trie?

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