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

Висоту дерева зазвичай визначають як:

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

Що робить операція peek (або top) стека?

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

Що зберігається для кожної вершини в поданні графа списками суміжності?

1. AРядок із V булевих значень
2. BНайкоротший шлях до кожної іншої вершини
3. CЗагальна кількість ребер у графі
4. DСписок сусідніх вершин

Яку умову збалансованості AVL-дерево підтримує в кожному вузлі?

1. AУсі листки розташовані рівно на однаковій глибині
2. BВисоти лівого та правого піддерев відрізняються щонайбільше на 1
3. CОбидва піддерева кожного вузла містять рівно однакову кількість вузлів
4. DКожен вузол пофарбовано в червоний або чорний колір

Префіксне дерево (trie) особливо ефективне для:

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

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

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

Яка вартість однієї операції find у найгіршому випадку в структурі union-find з n елементами без об'єднання за рангом і стиснення шляхів?

1. AO(α(n))
2. BO(log n)
3. CO(n)
4. DO(1)

Яке твердження про пірамідальне сортування (heapsort) правильне?

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