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

Что хранит отображение (map, словарь)?

1. AТолько значения в порядке вставки
2. BЗначения, отсортированные по размеру
3. CПары одинаковых ключей
4. DПары ключ–значение с уникальными ключами

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

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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

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

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

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

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

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

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

1. AO(log n)
2. BO(1)
3. CO(α(n))
4. DO(n)

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AДелать размер буфера степенью двойки
2. BХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
4. DХранить front и rear в одной переменной