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

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

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Геш-таблицю функцій

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

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

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

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

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

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

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

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