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

Что такое степень вершины в неориентированном графе?

1. AДлина самого длинного пути из неё
2. BЕё позиция в списке смежности
3. CЧисло вершин графа
4. DЧисло инцидентных ей рёбер

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

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

Что такое дек (deque, двусторонняя очередь)?

1. AОчередь, допускающая удаление только с конца
2. BОчередь, отсортированная по приоритету
3. CСтруктура, допускающая вставку и удаление с обоих концов
4. DДве отдельные очереди в одном массиве

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AДвоичная куча рёбер
2. BСписки смежности
3. CОдин отсортированный массив вершин
4. DМатрица смежности

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе i − 1
2. BВ индексе 2i + 1
3. CВ индексе ⌊i / 2⌋ + 1
4. DВ индексе ⌊(i − 1) / 2⌋

Какому свойству должно удовлетворять красно-чёрное дерево?

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

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

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