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

Как элементы массива хранятся в памяти?

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

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

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

Как называется операция очереди, удаляющая элемент из начала?

1. AEnqueue
2. BDequeue
3. CInsert
4. DPush

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(log n) из-за двоичного поиска
2. BO(1), потому что индекс известен
3. CO(n²), потому что каждый элемент сдвигается n раз
4. DO(n), потому что последующие элементы нужно сдвинуть

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

1. AO(E)
2. BO(log V)
3. CO(V + E)
4. DO(V²)

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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

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

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