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

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

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

Яка структура даних працює за принципом «останнім прийшов — першим вийшов» (LIFO)?

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

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

1. AЧитання першого елемента
2. BВставлення на початок
3. CВидалення головного елемента
4. DДоступ до елемента з індексом i

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

1. AЛінійне зондування
2. BМетод ланцюжків (separate chaining)
3. CПодвійне гешування
4. DКвадратичне зондування

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

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

Яке призначення сторожового (фіктивного, sentinel) вузла у зв'язному списку?

1. AНе дати списку зростати понад фіксовану максимальну кількість вузлів
2. BЗберігати кількість елементів
3. CЗробити список відсортованим
4. DСпростити код, усунувши особливі випадки на голові чи хвості

Яка властивість підтримує кожне B-дерево ідеально збалансованим?

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

Які операції підтримує дерево Фенвіка (binary indexed tree) над масивом із n чисел за O(log n)?

1. AСортування масиву та бінарний пошук
2. BВставлення елементів у будь-яку позицію
3. CЗнаходження медіани за O(1)
4. DЗапити префіксних сум і оновлення окремих елементів