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

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

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

Глибина вузла в дереві — це:

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

Де розташований найменший елемент бінарної мін-купи?

1. AУ крайньому лівому листку
2. BВ останній позиції масиву
3. CУ будь-якому листку, який треба знайти
4. DУ корені

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

1. AO(log V)
2. BO(E)
3. CO(1)
4. DO(V)

Що правильно щодо матриці суміжності неорієнтованого графа?

1. AВона завжди верхньотрикутна
2. BКожен рядок містить рівно одну 1
3. CЇї головна діагональ завжди містить одиниці
4. DВона симетрична відносно головної діагоналі

Що відбувається, коли геш-таблиця виконує повторне гешування (rehash) після того, як коефіцієнт заповнення перевищив поріг?

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

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

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

Який час роботи пошуку в ширину (BFS) у графі з V вершинами, що зберігається як матриця суміжності?

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