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

Що таке цикл у графі?

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. An (дерево перетворюється на зв'язний список)
2. B√n
3. Clog₂ n
4. D1

Як вставляють новий елемент у бінарну купу?

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

Яку структуру даних використовує виконувана програма, щоб відстежувати активні виклики функцій та їхні локальні змінні?

1. AБінарне дерево пошуку фреймів
2. BЧергу пам'яті купи
3. CСтек викликів
4. DГеш-таблицю функцій

У BST з коренем 50, лівим піддеревом 30 (діти 20, 40) і правим піддеревом 70 (діти 60, 80) корінь видаляють за допомогою наступника в симетричному порядку. Який ключ стає новим коренем?

1. A60
2. B70
3. C40
4. D80

Які операції підтримує дерево Фенвіка (binary indexed tree) над масивом із n чисел за O(log n)?

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