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

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

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

Что такое коллизия в хеш-таблице?

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

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

1. AГраф
2. BОчередь
3. CСтек
4. DХеш-множество

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

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

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

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

Какова стоимость вставки элемента в середину массива из n элементов?

1. AO(1), потому что индекс известен
2. BO(n), потому что последующие элементы нужно сдвинуть
3. CO(n²), потому что каждый элемент сдвигается n раз
4. DO(log n) из-за двоичного поиска

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

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

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

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