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

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

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. AЛинейное пробирование
2. BДвойное хеширование
3. CКвадратичное пробирование
4. DМетод цепочек (separate chaining)

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 6
2. BВ индексе 3
3. CВ индексе 4
4. DВ индексе 0

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A40
2. B50
3. C70
4. D20

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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