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

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

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

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

1. AКуча
2. BБинарное дерево
3. CОчередь
4. DСтек

Какую структуру обычно используют для реализации очереди с приоритетом?

1. AСтек
2. BНеупорядоченный односвязный список
3. CКучу
4. DСтроку

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

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

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

1. AСвязные списки всегда хранят элементы на диске
2. BМассивы требуют меньше инструкций для сравнения значений
3. CЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
4. DОбход массива занимает в сумме O(1), а связного списка — O(n)

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AMax-куча, упорядоченная по полустепени исхода
2. BОчередь (или любая коллекция) вершин с полустепенью захода 0
3. CСтек всех посещённых рёбер
4. DМатрица смежности, фиксирующая, какие вершины уже удалены