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

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

Що таке вузли-брати (siblings) у дереві?

1. AВузол і його батько
2. BВузли без дітей
3. CВузли на однаковій глибині в різних піддеревах
4. DВузли зі спільним батьком

Що таке листок у дереві?

1. AВузол рівно з однією дитиною
2. BВузол без дітей
3. CВузол без батька
4. DВузол із найбільшим значенням

Як знайти мінімальний ключ у бінарному дереві пошуку?

1. AІти від кореня лівими дітьми, доки лівої дитини не буде
2. BІти від кореня правими дітьми, доки правої дитини не буде
3. CВідвідати кожен листок і порівняти їх
4. DПодивитися лише на корінь

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

1. A1
2. Blog₂ n
3. Cn (дерево перетворюється на зв'язний список)
4. D√n

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

1. A40
2. B50
3. C20
4. D70

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

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

Який час роботи пошуку в ширину (BFS) у графі з V вершинами, що зберігається як матриця суміжності?

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