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

Що визначає бінарне дерево?

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

Геш-таблиця (hash table) зберігає дані у вигляді:

1. AДерева з упорядкованими ключами
2. BЛише відсортованого списку
3. CПар ключ–значення, розташування яких визначає геш-функція
4. DРядка фіксованої довжини

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

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

Що правильно щодо матриці суміжності неорієнтованого графа?

1. AВона завжди верхньотрикутна
2. BВона симетрична відносно головної діагоналі
3. CКожен рядок містить рівно одну 1
4. DЇї головна діагональ завжди містить одиниці

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

1. AЗбалансоване бінарне дерево пошуку
2. BГеш-таблиця
3. CНевідсортований зв'язний список
4. DСтек

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

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

Яка вартість однієї операції find у найгіршому випадку в структурі union-find з n елементами без об'єднання за рангом і стиснення шляхів?

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

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

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