Главная / Алгоритмы и дискретные структуры /
"Продвинутые" алгоритмы для школьников / Тест 6
"Продвинутые" алгоритмы для школьников - тест 6
Упражнение 1:
Номер 1
Задача о вершинном покрытии является
Ответ:
 (1) NP-полной 
 (2) модификативной 
 (3) терминальной 
Номер 2
Для доказательства NP-полноты в теории сложности может использоваться
Ответ:
 (1) задача об эйлеровом пути 
 (2) задача о гиппократовых луночках 
 (3) задача о вершинном покрытии 
Номер 3
Множество вершин S графа, такое что, у каждого ребра графа хотя бы один из концов входит в S, носит название
Ответ:
 (1) полином вершин 
 (2) матрица вершин 
 (3) вершинное покрытие 
Упражнение 2:
Номер 1
Число вершин, входящих в вершинное покрытие, является
Ответ:
 (1) размером 
 (2) порядком 
 (3) модулем 
Номер 2
Размером вершинного покрытия называется
Ответ:
 (1) модуль максимального веса ребра 
 (2) число вершин, входящих в вершинное покрытие 
 (3) наименьшее остовное поддерево 
Номер 3
От чего зависит размер вершинного покрытия?
Ответ:
 (1) от числа вершин 
 (2) от связности графа 
 (3) от количества ребер 
Упражнение 3:
Номер 1
Задача о вершинном покрытии сходна с задачей
Ответ:
 (1) о независимом наборе 
 (2) о контекстных связях 
 (3) об остовных деревьях 
Номер 2
Множество вершин S
является вершинным покрытием тогда и только тогда, когда его дополнение является
Ответ:
 (1) остовным поддеревом 
 (2) ориентированным графом 
 (3) независимым набором 
Номер 3
Граф с n
вершинами имеет вершинное покрытие размера k
тогда и только тогда, когда данный граф имеет незавимимый набор размера
Ответ:
 (1) n
 
 (2) k
 
 (3) n-k
 
Упражнение 4:
Номер 1
Существуют ли алгоритмы решения задачи о вершинном покрытии за полиномиальное время?
Ответ:
 (1) алгоритм Эйлера 
 (2) алгоритм Варда 
 (3) нет, не существуют 
Номер 2
Набор ребер, в котором все вершины различны, носит название
Ответ:
 (1) маркер 
 (2) контейнер 
 (3) паросочетание 
Номер 3
Из каких элементов состоит паросочетание?
Ответ:
 (1) из вершин 
 (2) из ребер 
 (3) из меток 
Упражнение 5:
Номер 1
Размер паросочетания определяется
Ответ:
 (1) числом ребер 
 (2) количеством вершин 
 (3) числом остовных поддеревьев 
Номер 2
Число ребер в паросочетании определяет
Ответ:
 (1) размер 
 (2) порядок 
 (3) модуль 
Номер 3
Если каждая вершина входит только в одно ребро, то паросочетание называется
Ответ:
 (1) конечным 
 (2) контекстным 
 (3) полным 
Упражнение 6:
Номер 1
Полное паросочетание возможно в графах
Ответ:
 (1) только с четным количеством вершин 
 (2) только с нечетным количеством вершин 
 (3) с любым количеством вершин 
Номер 2
Если взять совокупность всех вершин графа, будет ли она являться вершинным покрытием?
Ответ:
 (1) да, будет 
 (2) нет, не будет 
 (3) только для связных графов 
Номер 3
Множество вершин является независимым, если
Ответ:
 (1) нет ребер, соединяющих вершины этого множества 
 (2) они входят в остовное поддерево 
 (3) все вершины связаны ребрами одинакового веса 
Упражнение 7:
Номер 1
Если граф можно разбить на два множества, в которых не будет ребер, соединяющих его вершины, то такой граф будет называться
Ответ:
 (1) полным 
 (2) двудольным 
 (3) бинарным 
Номер 2
В двудольных графах нет циклов
Ответ:
 (1) четной длины 
 (2) нечетной длины 
 (3) как четной, так и нечетной длины 
Упражнение 8:
Номер 1
Если в графе нет циклов нечетной длины, то он является
Ответ:
 (1) двудольным 
 (2) орграфом 
 (3) контейнером 
Номер 2
Дополнением вершинного покрытия является
Ответ:
 (1) остовное дерево 
 (2) матрица инцидентности 
 (3) независимое множество 
Номер 3
Дополнением независимого множества является
Ответ:
 (1) вершинное покрытие 
 (2) матрица смежности 
 (3) контейнер связей 
Упражнение 9:
Номер 1
Минимальное вершинное покрытие больше или равно размеру
Ответ:
 (1) матрицы смежности 
 (2) максимального паросочетания 
 (3) поддерева связности 
Номер 2
Граф, в котором степень всех вершин не больше двух, является
Ответ:
 (1) несвязным 
 (2) двудольным 
 (3) маркированным 
Номер 3
Если в графе есть удлиняющая цепь, то размер паросочетания можно увеличить
Ответ:
 (1) на 1 
 (2) на квадрат числа вершин 
 (3) на бесконечное число 
Упражнение 10:
Номер 1
Паросочетание является максимальным тогда и только тогда, когда
Ответ:
 (1) нет удлиняющей цепи 
 (2) оно входит в остовное дерево 
 (3) отсутствуют петли графа 
Номер 2
Каким образом можно найти удлиняющую цепь?
Ответ:
 (1) маркировкой вершин 
 (2) поиском в глубину 
 (3) остовным деревом 
Номер 3
Время работы поиска в глубину оценивается выражением
Ответ:
 (1) O(V2)
 
 (2) O(logE)
 
 (3) O(ElogE)
 
Упражнение 11:
Номер 1
Каким выражением оценивается время работы алгоритма поиска вершинного покрытия?
Ответ:
 (1) O(V3)
 
 (2) O(V2)
 
 (3) O(V)
 
Номер 2
Время работы алгоритма поиска вершинного покрытия
Ответ:
 (1) меньше времени работы поиска в глубину 
 (2) больше времени работы поиска в глубину 
 (3) равно времени работы поиска в глубину 
Номер 3
Для чего используется алгоритм Куна?
Ответ:
 (1) для поиска вершинного покрытия 
 (2) для поиска остовного дерева 
 (3) для поиска минимальных путей 
Упражнение 12:
Номер 1
Каким выражением оценивается время работы алгоритма Куна?
Ответ:
 (1) O(V3)
 
 (2) O(logV)
 
 (3) O(V-E)
 
Номер 2
Время работы алгоритма Куна
Ответ:
 (1) меньше времени работы алгоритма поиска вершинного покрытия 
 (2) больше времени работы алгоритма поиска вершинного покрытия 
 (3) равно времени работы алгоритма поиска вершинного покрытия 
Номер 3
Верно ли то, что алгоритм Куна работает быстрее, чем поиск в глубину?
Ответ:
 (1) да, это верно 
 (2) нет, это неверно 
 (3) только для маркированных графов