игра брюс 2048
Главная / Алгоритмы и дискретные структуры / "Продвинутые" алгоритмы для школьников / Тест 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) только для маркированных графов 




Главная / Алгоритмы и дискретные структуры / "Продвинутые" алгоритмы для школьников / Тест 6