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

Що таке степінь вершини в неорієнтованому графі?

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

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

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

У якому порядку прямий обхід (preorder) бінарного дерева відвідує вузли?

1. AЛіве піддерево, потім праве піддерево, потім вузол
2. BВузол, потім ліве піддерево, потім праве піддерево
3. CЛіве піддерево, потім вузол, потім праве піддерево
4. DПо рівнях згори

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

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

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

1. AМетод ланцюжків (separate chaining)
2. BЛінійне зондування
3. CПодвійне гешування
4. DКвадратичне зондування

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

1. A70
2. B20
3. C50
4. D40

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

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

Яка структура даних забезпечує кеш LRU (least recently used) з операціями get і put за O(1)?

1. AОдин відсортований масив
2. BЛише бінарне дерево пошуку
3. CГеш-мапа в поєднанні з двозв'язним списком
4. DЛише стек