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

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

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

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

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

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

Який абстрактний тип даних використовує алгоритм Дейкстри, щоб обрати наступну вершину для обробки?

1. AМножину без упорядкування
2. BЧергу FIFO
3. CМін-чергу з пріоритетом
4. DСтек

Скільки вузлів має ідеальне бінарне дерево висоти h, якщо висоту рахують у ребрах?

1. Ah²
2. B2^h
3. C2^h+1 − 1
4. D2h + 1

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

1. A2i + 1
2. Bi + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

Яку гарантію щодо висоти дерева з n ключами дають правила червоно-чорного дерева?

1. AВисота щонайбільше n / 2
2. BВисота щонайбільше 2 log₂(n + 1)
3. CВисота рівно log₂ n
4. DВисота щонайбільше log₂ n + 1

Як визначити, чи містить однозв'язний список цикл, використовуючи O(1) додаткової пам'яті?

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