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

Что такое свойство max-кучи?

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

1. AЧисло хранимых элементов, делённое на число корзин
2. BЧисло корзин, делённое на среднюю длину хранимых ключей
3. CЧисло коллизий на данный момент
4. DВремя загрузки таблицы с диска

Какая операция медленная в массиве, но быстрая в начале связного списка?

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AХеш-функции
2. BОбхода графа
3. CОчереди фиксированного размера
4. DДвоичного дерева поиска

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

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

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

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

Какому свойству должно удовлетворять красно-чёрное дерево?

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

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

1. AДвигать один указатель на один шаг, а другой на два и проверять, встретятся ли они
2. BХранить каждый посещённый узел в хеш-множестве
3. CСчитать узлы, пока счёт не превысит поле длины списка
4. DОтсортировать список и искать повторы