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

Что такое узлы-братья (siblings) в дереве?

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

Что содержит указатель next последнего узла односвязного списка?

1. AЧисло узлов в списке
2. BNull (узла нет)
3. CАдрес первого узла
4. DАдрес предыдущего узла

Глубина узла в дереве — это:

1. AЧисло рёбер от этого узла до самого глубокого листа
2. BЧисло узлов в его поддереве
3. CЧисло рёбер от корня до этого узла
4. DЧисло потомков этого узла

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AХеш-функции
2. BОбхода графа
3. CДвоичного дерева поиска
4. DОчереди фиксированного размера

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

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

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

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

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AУдаляют всё поддерево
2. BПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
3. CЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
4. DМеняют его местами с корнем