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

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

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

Где находится наименьший элемент двоичной min-кучи?

1. AВ корне
2. BВ последней позиции массива
3. CВ самом левом листе
4. DВ каком-то листе, который придётся искать

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

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

Как вставляется новый элемент в двоичную кучу?

1. AЕго помещают в корень и опускают вниз
2. BЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
3. CВсю кучу перестраивают с нуля
4. DЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ двусвязном списке
2. BВ односвязном списке
3. CВ динамическом массиве
4. DВ отсортированном массиве

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

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

Как определить, есть ли цикл в односвязном списке, используя O(1) дополнительной памяти?

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