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

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

1. AЧитання останнього елемента за індексом
2. BВставлення на початок
3. CВизначення довжини масиву фіксованого розміру
4. DДоступ до 5-го елемента

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

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

Висоту дерева зазвичай визначають як:

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

AVL-дерева та червоно-чорні дерева гарантують:

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

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

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

Який абстрактний тип даних використовує алгоритм Дейкстри, щоб обрати наступну вершину для обробки?

1. AЧергу FIFO
2. BМін-чергу з пріоритетом
3. CСтек
4. DМножину без упорядкування

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

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

Скільки триває пошук довільного ключа в бінарній мін-купі з n елементів?

1. AO(1)
2. BO(n)
3. CO(log log n)
4. DO(log n)