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

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

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

1. AЧтение первого элемента
2. BДоступ к элементу с индексом i
3. CУдаление головного элемента
4. DВставка в начало

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

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

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

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

Как работает extract-min в двоичной min-куче?

1. AИщут новый минимум среди всех листьев
2. BПоследний элемент перемещают в корень и опускают вниз (sift down)
3. CУдаляют последний элемент массива
4. DУдаляют корень и сдвигают все элементы на одну позицию влево

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе 2i + 1
2. BВ индексе ⌊(i − 1) / 2⌋
3. CВ индексе ⌊i / 2⌋ + 1
4. DВ индексе i − 1

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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