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

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

1. An − 1
2. Bn
3. C2n
4. Dn + 1

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

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

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

1. AКуча
2. BОчередь
3. CБинарное дерево
4. DСтек

Префиксное дерево (trie) особенно эффективно для:

1. AСортировки чисел
2. BПоиска кратчайших путей
3. CХранения матриц
4. DПоиска по префиксу, например автодополнения

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

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

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

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

Ключи 5, 3, 8, 1 вставляются в таком порядке в пустую двоичную min-кучу на массиве. Каков итоговый массив?

1. A[1, 3, 5, 8]
2. B[1, 3, 8, 5]
3. C[1, 5, 8, 3]
4. D[3, 1, 8, 5]

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

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