Структуры данных: лист заданий с ответами

Что такое цикл в графе?

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AДоступ к элементу с индексом i
2. BУдаление головного элемента
3. CЧтение первого элемента
4. DВставка в начало

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

1. AСвязный список
2. BХеш-таблица
3. CОчередь
4. DСтек

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

1. Alog₂ n
2. B√n
3. C1
4. Dn (дерево превращается в связный список)

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 6
2. BВ индексе 3
3. CВ индексе 0
4. DВ индексе 4

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ динамическом массиве
2. BВ односвязном списке
3. CВ отсортированном массиве
4. DВ двусвязном списке

Почему в хеш-таблице с открытой адресацией удаление часто выполняют с помощью метки «надгробие» (tombstone)?

1. AЭто делает таблицу отсортированной
2. BНадгробия ускоряют хеширование
3. CУдалённые ключи нужно хранить вечно из соображений безопасности, поэтому ячейки нельзя использовать повторно
4. DОсвобождение ячейки могло бы разорвать последовательность пробирования для других ключей

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

1. AЗапросы префиксных сумм и обновления отдельного элемента
2. BСортировку массива и двоичный поиск
3. CПоиск медианы за O(1)
4. DВставку элементов в любую позицию