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

Що таке зважений граф?

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

Яка структура даних працює за принципом «першим прийшов — першим вийшов» (FIFO)?

1. AБінарне дерево
2. BКупа
3. CЧерга
4. DСтек

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

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

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

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

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

1. Ah²
2. B2^h
3. C2h + 1
4. D2^h+1 − 1

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

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

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

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

Якій властивості має відповідати червоно-чорне дерево?

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