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

В двоичном дереве поиска значения в левом поддереве узла:

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

Где находится наименьший элемент двоичной min-кучи?

1. AВ каком-то листе, который придётся искать
2. BВ корне
3. CВ самом левом листе
4. DВ последней позиции массива

В каком порядке обратный обход (postorder) двоичного дерева посещает узлы?

1. AЛевое поддерево, затем правое поддерево, затем узел
2. BПравое поддерево, затем узел, затем левое поддерево
3. CУзел, затем левое поддерево, затем правое поддерево
4. DЛевое поддерево, затем узел, затем правое поддерево

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

1. AСтек
2. BКучу
3. CОчередь
4. DТолько хеш-таблицу

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

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

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

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

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AO(n²)
2. BРовно O(log n)
3. CO(α(n)), обратная функция Аккермана, практически константа
4. DO(n)

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

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