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

Яка операція повільна в масиві, але швидка на початку зв'язного списку?

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

Що зберігає відображення (map, словник)?

1. AЛише значення в порядку вставлення
2. BЗначення, відсортовані за розміром
3. CПари ключ–значення з унікальними ключами
4. DПари однакових ключів

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

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

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

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

Яку структуру даних використовує виконувана програма, щоб відстежувати активні виклики функцій та їхні локальні змінні?

1. AСтек викликів
2. BЧергу пам'яті купи
3. CБінарне дерево пошуку фреймів
4. DГеш-таблицю функцій

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

1. A40
2. B50
3. C70
4. D20

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

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

Видалення вузла з двома дітьми з бінарного дерева пошуку зазвичай виконують так:

1. AПеребудовують піддерево під ним з нуля й повторно вставляють усі ключі, які воно містило
2. BЗамінюють його in-order наступником (або попередником) і видаляють той вузол
3. CМіняють його місцями з коренем
4. DВидаляють усе піддерево