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

Що таке степінь вершини в неорієнтованому графі?

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

Що таке дек (deque, двостороння черга)?

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

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

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

Кільцевий буфер (ring buffer) зазвичай використовують для реалізації:

1. AЧерги фіксованого розміру
2. BГеш-функції
3. CБінарного дерева пошуку
4. DОбходу графа

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

1. Ai + 1
2. B(i + 1) mod n
3. C2i + 1
4. D(i − 1) mod n

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

1. AВ індексі ⌊(i − 1) / 2⌋
2. BВ індексі i − 1
3. CВ індексі ⌊i / 2⌋ + 1
4. DВ індексі 2i + 1

Для кожного елемента масиву потрібно знайти наступний більший елемент праворуч від нього за загальний час O(n). Яка структура допоможе?

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

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

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