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

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

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

Що таке листок у дереві?

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

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

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

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

1. Ai + 1 і i + 2
2. B2i + 1 і 2i + 2
3. Ci/2 і i/2 + 1
4. D2i і 2i + 1

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

1. An (дерево перетворюється на зв'язний список)
2. B1
3. Clog₂ n
4. D√n

Застосунку потрібен швидкий пошук, а також виведення ключів у відсортованому порядку та відповіді на запити діапазону. Яка структура підходить найкраще?

1. AСтек
2. BЗбалансоване бінарне дерево пошуку
3. CНевідсортований зв'язний список
4. DГеш-таблиця

Чим radix-дерево (стиснене префіксне дерево) краще за звичайне trie?

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

Чому сервер може обирати свою геш-функцію випадково з універсального сімейства?

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