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

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

1. AДве копии данных и один указатель
2. BДанные, указатель на следующий узел и указатель на предыдущий узел
3. CДанные и только указатель на следующий узел
4. DДанные и два указателя: один на следующий узел и один на узел после него

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

1. AEnqueue
2. BPeek
3. CPop
4. DPush

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

1. AОчередь
2. BСтек
3. CХеш-множество
4. DГраф

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

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

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

1. AКвадратичное пробирование
2. BДвойное хеширование
3. CМетод цепочек (separate chaining)
4. DЛинейное пробирование

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

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

Дерево отрезков (segment tree) обычно используют для:

1. AРеализации стека
2. BОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)
3. CХранения рёбер графа
4. DСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева

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

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