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

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

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

Геш-таблиця (hash table) зберігає дані у вигляді:

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. A0,5
2. BМаксимуму немає
3. C2
4. D1

Скільки пам'яті займає матриця суміжності графа з V вершинами?

1. AO(log V)
2. BO(V + E)
3. CO(V²)
4. DO(E)

Чим radix-дерево (стиснене префіксне дерево) краще за звичайне trie?

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

Для кожного елемента масиву потрібно знайти наступний більший елемент праворуч від нього за загальний час O(n). Яка структура допоможе?

1. AГеш-таблиця всіх елементів
2. BЧерга, що містить кожну пару елементів
3. CБінарне дерево пошуку, перебудоване для кожного елемента
4. DСтек, що зберігає елементи, які чекають на свою відповідь