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

Какую структуру обычно используют для реализации очереди с приоритетом?

1. AНеупорядоченный односвязный список
2. BСтек
3. CСтроку
4. DКучу

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

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

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

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

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

1. AЧтобы хранить число элементов
2. BЧтобы упростить код, убрав особые случаи в голове или хвосте
3. CЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
4. DЧтобы список был отсортирован

Как вставляется новый элемент в двоичную кучу?

1. AВсю кучу перестраивают с нуля
2. BЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
4. DЕго помещают в корень и опускают вниз

Дерево отрезков (segment tree) обычно используют для:

1. AОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
2. BХранения рёбер графа
3. CРеализации стека
4. DСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева

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

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