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

Що містить кожен вузол двозв'язного списку?

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Купи ніколи не містять понад 100 елементів
2. BУсі ключі в купі однакові
3. CМасиви автоматично зберігають ключі відсортованими, тож вказівники не потрібні
4. DЦе повне бінарне дерево, тож позиції визначаються простими формулами індексів

Геш-таблиця розміру 7 використовує h(k) = k mod 7 і лінійне зондування. Після вставлення 10 де буде збережено 17?

1. AВ індексі 6
2. BВ індексі 3
3. CВ індексі 0
4. DВ індексі 4

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

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

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

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

Яка пара обходів завжди однозначно визначає бінарне дерево з різними ключами?

1. AЛише прямий обхід
2. BЛише обхід по рівнях
3. CПрямий і зворотний обходи
4. DПрямий і симетричний обходи