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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

1. AУзел, затем левое поддерево, затем правое поддерево
2. BПо уровням сверху вниз
3. CЛевое поддерево, затем правое поддерево, затем узел
4. DЛевое поддерево, затем узел, затем правое поддерево

Что хранится для каждой вершины в представлении графа списками смежности?

1. AОбщее число рёбер графа
2. BСтрока из V булевых значений
3. CКратчайший путь до каждой другой вершины
4. DСписок соседних вершин

Что такое степень вершины в неориентированном графе?

1. AЧисло инцидентных ей рёбер
2. BЕё позиция в списке смежности
3. CЧисло вершин графа
4. DДлина самого длинного пути из неё

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

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

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

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

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

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

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

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

1. AС возможными ложноотрицательными, но без ложноположительных результатов
2. BС возможными ложноположительными, но без ложноотрицательных результатов
3. CТолько для чисел
4. DВсегда точно