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

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

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

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

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

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

1. AЧерга
2. BСтек
3. CГеш-множина
4. DГраф

Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?

1. AO(L × n)
2. BO(log n), де n — кількість слів
3. CO(L), незалежно від кількості збережених слів
4. DO(n), де n — кількість слів

Симетричний обхід (in-order) бінарного дерева пошуку відвідує ключі:

1. AПо рівнях
2. BУ порядку зростання (відсортовано)
3. CУ порядку вставлення
4. DЗавжди в порядку спадання

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

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

Яка структура дає змогу обчислити максимум кожного вікна розміру k у масиві за загальний час O(n)?

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

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

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