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

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

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Обход массива занимает в сумме O(1), а связного списка — O(n)
4. DСвязные списки всегда хранят элементы на диске

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A50
2. B20
3. C40
4. D70

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

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

Что делает косое дерево (splay tree) после каждого обращения?

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