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

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

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

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

1. APush
2. BInsert
3. CDequeue
4. DEnqueue

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

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

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

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

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який зворотний обхід (postorder)?

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D1 2 4 5 3

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

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

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

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

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

1. AРівні геш-значення означають рівні ключі
2. BГеш-значення мусять бути простими числами
3. CРівні ключі мусять мати рівні геш-значення
4. DРізні ключі мусять мати різні геш-значення