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

Яку структуру зазвичай використовують для реалізації черги з пріоритетом?

1. AСтек
2. BНевпорядкований однозв'язний список
3. CКупу
4. DРядок

Що таке цикл у графі?

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

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

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

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

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

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

1. AБінарне дерево пошуку
2. BГеш-таблицю
3. CЧергу
4. DСтек

Симетричний обхід (in-order) бінарного дерева пошуку відвідує ключі:

1. AПо рівнях
2. BУ порядку зростання (відсортовано)
3. CУ порядку вставлення
4. DЗавжди в порядку спадання

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

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

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

1. AЩоб масив залишався відсортованим
2. BБо розподілювач пам'яті може звільняти пам'ять лише чвертями блока
3. CБо зменшення вдвічі за половинного заповнення призвело б до втрати елементів
4. DЩоб уникнути повторних змін розміру, коли push і pop чергуються біля межі