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

Яку структуру зазвичай використовують для реалізації черги з пріоритетом?

1. AКупу
2. BНевпорядкований однозв'язний список
3. CСтек
4. DРядок

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

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

Що робить операція peek (або top) стека?

1. AВидаляє верхній елемент і повертає його
2. BВидаляє всі елементи зі стека
3. CПовертає верхній елемент, не видаляючи його
4. DПовертає нижній елемент стека

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

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

Чому бінарну купу можна зберігати в масиві без жодних вказівників?

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

Вузол бінарного дерева пошуку має праве піддерево. Де розташований його наступник у симетричному порядку (in-order successor)?

1. AЗавжди його батько
2. BКрайній правий вузол його лівого піддерева
3. CКрайній лівий вузол його правого піддерева
4. DЗавжди його права дитина

Часова складність операції decrease-key у бінарній купі (за відомої позиції елемента) становить:

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

Чому сервер може обирати свою геш-функцію випадково з універсального сімейства?

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