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

Граф состоит из:

1. AСтрок и столбцов
2. BТолько корня и листьев
3. CВершин (узлов), соединённых рёбрами
4. DТолько ключей и хешей

Какая структура данных используется для обхода дерева по уровням (level-order)?

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

Что содержит указатель next последнего узла односвязного списка?

1. AЧисло узлов в списке
2. BNull (узла нет)
3. CАдрес первого узла
4. DАдрес предыдущего узла

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

1. AКвадратичное пробирование
2. BЛинейное пробирование
3. CМетод цепочек (separate chaining)
4. DДвойное хеширование

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AВысоту O(log n) благодаря перебалансировке
2. BПоиск за константное время в любом случае
3. CХранение ключей в порядке вставки
4. DЧто ни у одного узла нет двух потомков

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

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

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

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