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

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

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

Як називається операція стека, що додає елемент на вершину?

1. APop
2. BPush
3. CPeek
4. DEnqueue

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

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

Чому бінарну купу можна зберігати в масиві без жодних вказівників?

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

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

1. AМетод ланцюжків (separate chaining)
2. BЛінійне зондування
3. CПодвійне гешування
4. DКвадратичне зондування

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

1. A2i + 1
2. B(i + 1) mod n
3. C(i − 1) mod n
4. Di + 1

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

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

Вставлення ключа в AVL-дерево робить ліве піддерево вузла надто високим, причому новий ключ потрапив у ліве піддерево його лівої дитини (випадок «ліво-ліво»). Яке виправлення застосовують?

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