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

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

1. AБінарне дерево
2. BКупа
3. CЧерга
4. DСтек

Що робить геш-функція в геш-таблиці?

1. AВідображає ключ в індекс у таблиці
2. BРахує, скільки ключів збережено
3. CСортує ключі в таблиці
4. DШифрує значення в таблиці

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

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

Скільки пам'яті займає матриця суміжності графа з V вершинами?

1. AO(V + E)
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Вставляють його на відсортовану позицію, зсуваючи всі більші елементи на одне місце праворуч

Дерево відрізків (segment tree) зазвичай використовують для:

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

Якій властивості має відповідати червоно-чорне дерево?

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