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

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

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

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

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

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

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

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

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

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

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

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

1. An (дерево перетворюється на зв'язний список)
2. B1
3. Clog₂ n
4. D√n

У циклічному буфері front == rear може означати як порожній, так і заповнений буфер. Який поширений спосіб їх розрізнити?

1. AРобити розмір буфера степенем двійки
2. BЗавжди очищати буфер щоразу, коли front дорівнює rear, тож стан — порожній
3. CЗберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
4. DЗберігати front і rear в одній змінній

Фільтр Блума може відповісти на запитання «чи належить цей елемент множині?»:

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