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

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

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

Что такое взвешенный граф?

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

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

1. AO(E)
2. BO(V + E)
3. CO(V²)
4. DO(log V)

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

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

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. A2i + 1 и 2i + 2
2. Bi + 1 и i + 2
3. Ci/2 и i/2 + 1
4. D2i и 2i + 1

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

1. AЗапросы префиксных сумм и обновления отдельного элемента
2. BСортировку массива и двоичный поиск
3. CПоиск медианы за O(1)
4. DВставку элементов в любую позицию

Какая пара обходов всегда однозначно определяет двоичное дерево с различными ключами?

1. AОдин только прямой
2. BПрямой и симметричный (preorder и inorder)
3. CОдин только обход по уровням
4. DПрямой и обратный (preorder и postorder)