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

Что определяет двоичное дерево?

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

Высота дерева обычно определяется как:

1. AЧисло рёбер на самом длинном пути от корня до листа
2. BЧисло листьев в дереве
3. CЧисло потомков корня
4. DОбщее число узлов в дереве, считая корень и каждый лист

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

1. ADequeue
2. BPush
3. CEnqueue
4. DInsert

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A(i + 1) mod n
2. B(i − 1) mod n
3. Ci + 1
4. D2i + 1

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

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

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

1. AЗначения хеша должны быть простыми числами
2. BРавные ключи должны иметь равные значения хеша
3. CРазные ключи должны иметь разные значения хеша
4. DИз равенства хешей следует равенство ключей

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
2. BMax-куча размера k, корень которой заменяется, когда приходит меньшее значение
3. CОтсортированный массив всех n значений
4. DОчередь FIFO последних k значений