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

В однозв'язному списку кожен вузол містить:

1. AЛише дані
2. BДані та посилання на наступний вузол
3. CДані та індекс
4. DДані та посилання на всі інші вузли

Скільки ребер має дерево з n вузлами?

1. An − 1
2. Bn + 1
3. C2n
4. Dn

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

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

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

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

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

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C4 5 2 3 1
4. D1 2 3 4 5

Яка вартість вставлення елемента в середину масиву з n елементів?

1. AO(log n) через бінарний пошук
2. BO(1), бо індекс відомий
3. CO(n), бо наступні елементи доводиться зсувати
4. DO(n²), бо кожен елемент переміщується n разів

Дерево відрізків (segment tree) зазвичай використовують для:

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

Потрібно зберігати k найменших значень із потоку n чисел, використовуючи O(k) пам'яті. Який підхід працює за час O(n log k)?

1. AМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
2. BВідсортований масив усіх n значень
3. CМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення
4. DЧерга FIFO з останніх k значень