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

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

1. AЧитання останнього елемента за індексом
2. BВизначення довжини масиву фіксованого розміру
3. CДоступ до 5-го елемента
4. DВставлення на початок

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

1. AДані та лише вказівник на наступний вузол
2. BДані та два вказівники: один на наступний вузол і один на вузол після нього
3. CДві копії даних і один вказівник
4. DДані, вказівник на наступний вузол і вказівник на попередній вузол

Яка головна відмінність між статичним і динамічним масивом?

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

AVL-дерева та червоно-чорні дерева гарантують:

1. AЗберігання ключів у порядку вставлення
2. BЩо жоден вузол не має двох дітей
3. CВисоту O(log n) завдяки перебалансуванню
4. DПошук за сталий час у будь-якому випадку

Геш-таблиця розміру 7 використовує h(k) = k mod 7 і лінійне зондування. Після вставлення 10 де буде збережено 17?

1. AВ індексі 6
2. BВ індексі 0
3. CВ індексі 4
4. DВ індексі 3

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

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

Потрібно зберігати k найменших значень із потоку n чисел, використовуючи O(k) пам'яті. Який підхід працює за час O(n log k)?

1. AВідсортований масив усіх n значень
2. BЧерга FIFO з останніх k значень
3. CМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
4. DМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення

Які операції підтримує дерево Фенвіка (binary indexed tree) над масивом із n чисел за O(log n)?

1. AВставлення елементів у будь-яку позицію
2. BЗапити префіксних сум і оновлення окремих елементів
3. CЗнаходження медіани за O(1)
4. DСортування масиву та бінарний пошук