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

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

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

Геш-таблиця (hash table) зберігає дані у вигляді:

1. AЛише відсортованого списку
2. BДерева з упорядкованими ключами
3. CПар ключ–значення, розташування яких визначає геш-функція
4. DРядка фіксованої довжини

В однозв'язному списку кожен вузол містить:

1. AДані та індекс
2. BДані та посилання на всі інші вузли
3. CДані та посилання на наступний вузол
4. DЛише дані

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

1. AВ індексі ⌊i / 2⌋ + 1
2. BВ індексі i − 1
3. CВ індексі 2i + 1
4. DВ індексі ⌊(i − 1) / 2⌋

Чому обхід масиву на практиці часто значно швидший, ніж обхід зв'язного списку такої самої довжини?

1. AМасиви використовують менше інструкцій для порівняння значень
2. BЗв'язні списки завжди зберігають елементи на диску
3. CОбхід масиву загалом має складність O(1), а обхід зв'язного списку — O(n)
4. DЕлементи масиву розташовані суцільно, тож добре використовують кеш процесора

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

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

Скільки триває пошук довільного ключа в бінарній мін-купі з n елементів?

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

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

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