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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

1. AСтек
2. BХеш-таблица
3. CСвязный список
4. DОчередь

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

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

Как элементы массива хранятся в памяти?

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

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

1. AЧтобы упростить код, убрав особые случаи в голове или хвосте
2. BЧтобы список был отсортирован
3. CЧтобы хранить число элементов
4. DЧтобы список не мог вырасти сверх фиксированного максимального числа узлов

Как найти минимальный ключ в двоичном дереве поиска?

1. AИдти от корня по правым потомкам, пока правого потомка не окажется
2. BПосмотреть только на корень
3. CОбойти все листья и сравнить их
4. DИдти от корня по левым потомкам, пока левого потомка не окажется

Что верно для матрицы смежности неориентированного графа?

1. AНа её главной диагонали всегда стоят единицы
2. BОна симметрична относительно главной диагонали
3. CОна всегда верхнетреугольная
4. DВ каждой строке ровно одна 1

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
2. BОчередь FIFO последних k значений
3. CMax-куча размера k, корень которой заменяется, когда приходит меньшее значение
4. DОтсортированный массив всех n значений

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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