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

Граф складається з:

1. AЛише кореня та листків
2. BВершин (вузлів), з'єднаних ребрами
3. CРядків і стовпців
4. DЛише ключів і гешів

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

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

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

1. AEnqueue
2. BPeek
3. CPush
4. DPop

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

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

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

1. AМаксимуму немає
2. B2
3. C1
4. D0,5

Як вставляють новий елемент у бінарну купу?

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

Чому в геш-таблиці з відкритою адресацією видалення часто виконують за допомогою позначки «надгробок» (tombstone)?

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

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

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