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

Що таке властивість макс-купи?

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

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

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

Яка структура даних найкраще підходить для функції «скасувати» (undo) у текстовому редакторі?

1. AЧерга
2. BГеш-множина
3. CСтек
4. DГраф

Чергу реалізовано двома стеками: push у стек «in» і pop зі стека «out», який поповнюють із «in», коли він порожній. Яка амортизована вартість однієї операції?

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

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

1. A(i + 1) mod n
2. B(i − 1) mod n
3. C2i + 1
4. Di + 1

Яку умову збалансованості AVL-дерево підтримує в кожному вузлі?

1. AВисоти лівого та правого піддерев відрізняються щонайбільше на 1
2. BКожен вузол пофарбовано в червоний або чорний колір
3. CОбидва піддерева кожного вузла містять рівно однакову кількість вузлів
4. DУсі листки розташовані рівно на однаковій глибині

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

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

Яка структура дає змогу обчислити максимум кожного вікна розміру k у масиві за загальний час O(n)?

1. AОднозв'язний список елементів вікна
2. BМін-купа, перебудована для кожного вікна
3. CВідсортований масив, що оновлюється зсувом
4. DДек, що зберігає індекси в порядку спадання значень