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

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

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

Що містить кожен вузол двозв'язного списку?

1. AДві копії даних і один вказівник
2. BДані та лише вказівник на наступний вузол
3. CДані та два вказівники: один на наступний вузол і один на вузол після нього
4. DДані, вказівник на наступний вузол і вказівник на попередній вузол

В однозв'язному списку кожен вузол містить:

1. AДані та індекс
2. BДані та посилання на всі інші вузли
3. CДані та посилання на наступний вузол
4. DЛише дані

AVL-дерева та червоно-чорні дерева гарантують:

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

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

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

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

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

Яка пара обходів завжди однозначно визначає бінарне дерево з різними ключами?

1. AЛише прямий обхід
2. BПрямий і зворотний обходи
3. CЛише обхід по рівнях
4. DПрямий і симетричний обходи

Що робить розширюване дерево (splay tree) після кожного звертання?

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