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

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

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

Что такое лист дерева?

1. AУзел без потомков
2. BУзел без родителя
3. CУзел ровно с одним потомком
4. DУзел с наибольшим значением

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

1. ADequeue
2. BInsert
3. CPush
4. DEnqueue

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

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

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

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ односвязном списке
2. BВ динамическом массиве
3. CВ отсортированном массиве
4. DВ двусвязном списке

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

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

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

1. AЧтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы
2. BПотому что распределитель памяти может освобождать память только четвертями блока
3. CПотому что уменьшение вдвое при половинном заполнении привело бы к потере элементов
4. DЧтобы массив оставался отсортированным