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

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

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

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

Скільки ребер має дерево з n вузлами?

1. A2n
2. Bn
3. Cn + 1
4. Dn − 1

Як працює extract-min у бінарній мін-купі?

1. AОстанній елемент переміщують у корінь і просіюють униз
2. BШукають новий мінімум серед усіх листків
3. CВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
4. DВидаляють останній елемент масиву

Префіксне дерево (trie) особливо ефективне для:

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

Яке призначення сторожового (фіктивного, sentinel) вузла у зв'язному списку?

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

Чому зі стандартного фільтра Блума не можна просто видаляти елементи, очищаючи їхні біти?

1. AФільтри Блума зберігають повні елементи, і після гешування їх неможливо знайти знову
2. BВидалення підвищило б частку хибнопозитивних результатів до 100%
3. CБіти у фільтрі Блума не можна змінювати після створення
4. DЦі біти можуть належати й іншим елементам, що спричинило б хибнонегативні результати

Яке твердження про пірамідальне сортування (heapsort) правильне?

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