Базовые и "продвинутые" алгоритмы для школьников

Упражнение 1:

Номер 1

Ациклический подграф данного графа, в который входят все вершины данного графа и в котором столько же компонент связности, сколько в данном графе, носит название

Ответ:

(1) остовный лес

(2) модульный лес

(3) бор

Номер 2

Что представляет собой остовный лес?

Ответ:

(1) комплексный орграф

(2) массивный мультиграф

(3) ациклический подграф

Номер 3

Количество компонент связности остовного леса

Ответ:

(1) больше количества компонент связности графа

(2) меньше количества компонент связности графа

(3) равно количеству компонент связности графа

Упражнение 2:

Номер 1

Для связных графов остовный лес называется

Ответ:

(1) остовное дерево

(2) остовный комплекс

(3) остовный контейнер

Номер 2

Скелет графа - это

Ответ:

(1) остовное дерево

(2) компонента связности

(3) минимальный эйлеров путь

Номер 3

Сколько вершин графа содержит остовный лес?

Ответ:

(1) половину

(2) одну

(3) все

Упражнение 3:

Номер 1

В системе непересекающихся множеств каждому подмножеству назначается

Ответ:

(1) итератор

(2) представитель

(3) модификатор

Номер 2

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

Ответ:

(1) Union

(2) Find

(3) Define

Номер 3

Из приведенных ниже записей выделите операции, которыми определяется абстрактная структура данных в системе непересекающихся множеств:

Ответ:

(1) Rewrite

(2) Find

(3) MakeSet

Упражнение 4:

Номер 1

Система непересекающихся множеств очень удобна для хранения

Ответ:

(1) маркированных вершин

(2) компонентов связности в графах

(3) кратчайших путей

Номер 2

Для чего в СНМ используется операция MakeSet?

Ответ:

(1) для создания элемента

(2) для вывода данных

(3) для формирования остовного дерево

Номер 3

Для чего корень более низкого дерева вешается под корень более высокого дерева во время операции Union на СНМ?

Ответ:

(1) для балансировки дерева

(2) для составления остовного дерева

(3) для формирования матрицы смежности

Упражнение 5:

Номер 1

Глубина каждого поддерева T при использовании Union-By-Size на СНМ не может превысить величину

Ответ:

(1) log|T|

(2) 2T

(3) 2T-1

Номер 2

При использовании эвристики Union-By-Size worst-case-время операции Find составляет

Ответ:

(1) O(logn)

(2) O(n)

(3) O(1)

Номер 3

Для эффективной имплементации при использовании эвристики Union-By-Size предлагается сохранять в корне

Ответ:

(1) компоненту связности

(2) количество узлов в дереве

(3) ключ доступа к вершинам дерева

Упражнение 6:

Номер 1

Чтобы ускорить операцию Find(x) на СНМ используется

Ответ:

(1) сжатие путей

(2) трассировка компонент связности

(3) стек вершин

Номер 2

Функция Аккермана возвращает

Ответ:

(1) натуральное число

(2) комплексное число

(3) массив вершин

Номер 3

Входом функции Аккермана служит

Ответ:

(1) массив вершин

(2) пара целых неотрицательных чисел

(3) компонента связности

Упражнение 7:

Номер 1

Для чего используется алгоритм Краскала?

Ответ:

(1) для формирования матрицы смежности

(2) для нахождения остовного леса минимального веса

(3) для формирования компоненты связности

Номер 2

Для нахождения остовного леса минимального веса в данном графе используется

Ответ:

(1) алгоритм Краскала

(2) алгоритм Коши

(3) алгоритм Эйлера

Номер 3

Результатом работы алгоритма Краскала является

Ответ:

(1) остовный лес

(2) матрица достижимости

(3) набор вершин

Упражнение 8:

Номер 1

Сколько времени потребует сортировка ребер графа по весу?

Ответ:

(1) O(Elog(E))

(2) O(log(E))

(3) O(E)

Номер 2

Общее время работы Алгоритма Краскала составляет

Ответ:

(1) O(1)

(2) O(Elog(E))

(3) O(E²)

Номер 3

Подграф данного графа, содержащий все его вершины и множество рёбер минимального веса, является его

Ответ:

(1) матрицей соответствия

(2) остовным лесом минимального веса

(3) компонентой модульности

Упражнение 9:

Номер 1

Алгоритм Краскала является частным случаем алгоритма

Ответ:

(1) Коши

(2) Радо-Эдмондса

(3) Гамильтона

Номер 2

Сумма пропускных способностей рёбер стока и истока представляет собой

Ответ:

(1) размер компоненты связности

(2) величину разреза графа

(3) диагональ матрицы смежности

Номер 3

Множество рёбер, удаление которых делит граф на два изолированных подграфа, носит название

Ответ:

(1) модуляция графа

(2) разрез графа

(3) компонента графа

Упражнение 10:

Номер 1

Верно ли то, что линии разреза графа могут пересекать произвольное число ребер и хорд?

Ответ:

(1) да, верно

(2) нет, неверно

(3) только в циклическом графе

Номер 2

Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она при произвольном пересечении хорд пересекала

Ответ:

(1) только одну ветвь графа

(2) не менее двух ветвей графа

(3) все верви графа

Номер 3

Может ли изолированный подграф, получившийся после разреза графа быть отдельным узлом?

Ответ:

(1) нет, это исключено

(2) да, может

(3) только в комплексном графе

Упражнение 11:

Номер 1

Какие условия должны быть выполнены для потока в графе?

Ответ:

(1) условие баланса

(2) условие допустимости

(3) условие возврата

Номер 2

В условии допустимости для потока в графе используется

Ответ:

(1) количество вершин

(2) пропускная способность дуги

(3) массив итераторов рекурсии

Номер 3

Поток в графе зависит

Ответ:

(1) от дуг графа

(2) от матрицы совместимости

(3) от компоненты смежности

Упражнение 12:

Номер 1

О чем говорит теорема Форда-Фалкерсона?

Ответ:

(1) о максимальном потоке в графе

(2) о минимальном потоке в графе

(3) об оптимальном потоке в графе

Номер 2

Согласно теореме Форда-Фалкерсона величина максимального потока равна величине

Ответ:

(1) минимального разреза

(2) компоненты связности

(3) терминальной матрицы ребер

Номер 3

Любой поток между вершинами

Ответ:

(1) больше любого сечения

(2) равен любому сечению

(3) меньше или равен любому сечению

Базовые и "продвинутые" алгоритмы для школьников - тест 6