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

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

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

Яка структура даних працює за принципом «останнім прийшов — першим вийшов» (LIFO)?

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

У якому порядку прямий обхід (preorder) бінарного дерева відвідує вузли?

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

Яке призначення сторожового (фіктивного, sentinel) вузла у зв'язному списку?

1. AНе дати списку зростати понад фіксовану максимальну кількість вузлів
2. BЗберігати кількість елементів
3. CСпростити код, усунувши особливі випадки на голові чи хвості
4. DЗробити список відсортованим

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

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

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

1. AБінарне дерево пошуку
2. BГеш-таблицю
3. CЧергу
4. DСтек

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

1. AРівні ключі мусять мати рівні геш-значення
2. BГеш-значення мусять бути простими числами
3. CРізні ключі мусять мати різні геш-значення
4. DРівні геш-значення означають рівні ключі

Структура union-find (система неперетинних множин) з об'єднанням за рангом і стисненням шляху має амортизовану вартість операції:

1. AO(n²)
2. BРівно O(log n)
3. CO(α(n)), обернена функція Аккермана, практично стала
4. DO(n)