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

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

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

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

1. AEnqueue
2. BPush
3. CPop
4. DPeek

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

1. AКількість вузлів у списку
2. BАдресу першого вузла
3. CАдресу попереднього вузла
4. DNull (жодного вузла)

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

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

Яка вартість вставлення елемента в середину масиву з n елементів?

1. AO(n), бо наступні елементи доводиться зсувати
2. BO(1), бо індекс відомий
3. CO(n²), бо кожен елемент переміщується n разів
4. DO(log n) через бінарний пошук

Як вставляють новий елемент у бінарну купу?

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

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

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

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

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