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

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

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

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

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

Что такое цикл в графе?

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

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

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

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

1. AСтек
2. BМножество без упорядочения
3. CОчередь FIFO
4. DОчередь с приоритетом по минимуму

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A1
2. B2
3. C0,5
4. DМаксимума нет

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

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

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

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