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

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

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

Что такое свойство max-кучи?

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

В односвязном списке каждый узел содержит:

1. AДанные и ссылку на следующий узел
2. BТолько данные
3. CДанные и ссылки на все остальные узлы
4. DДанные и индекс

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

1. AПоиск за константное время в любом случае
2. BВысоту O(log n) благодаря перебалансировке
3. CХранение ключей в порядке вставки
4. DЧто ни у одного узла нет двух потомков

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

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

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

1. AВсегда очищать буфер, когда front равен rear, так что состояние — пустой
2. BХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
3. CДелать размер буфера степенью двойки
4. DХранить front и rear в одной переменной

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

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