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

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

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

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

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

Сколько рёбер в дереве с n узлами?

1. An + 1
2. Bn
3. Cn − 1
4. D2n

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

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

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

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

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

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

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

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

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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