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

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

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

Що зберігається для кожної вершини в поданні графа списками суміжності?

1. AРядок із V булевих значень
2. BСписок сусідніх вершин
3. CНайкоротший шлях до кожної іншої вершини
4. DЗагальна кількість ребер у графі

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

1. AВставлення на початок
2. BЧитання першого елемента
3. CВидалення головного елемента
4. DДоступ до елемента з індексом i

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

1. AПодивитися лише на корінь
2. BІти від кореня правими дітьми, доки правої дитини не буде
3. CІти від кореня лівими дітьми, доки лівої дитини не буде
4. DВідвідати кожен листок і порівняти їх

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

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

Яке значення постфіксного виразу 3 4 + 2 * ?

1. A14
2. B10
3. C11
4. D24

Яку проблему лінійного зондування переважно зменшує подвійне гешування?

1. AВартість O(n) читання значення ключа
2. BПервинну кластеризацію, коли утворюються довгі серії зайнятих комірок
3. CПотребу в геш-функції
4. DПотребу зберігати ключі в таблиці

Для чого використовують структуру union-find в алгоритмі Краскала для мінімального кістякового дерева?

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