Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы



Скачать 105.1 Kb.
Дата11.10.2012
Размер105.1 Kb.
ТипДокументы

Ответы на экзаменационные вопросы интернет-курсов ИНТУИТ (INTUIT) : Графы и алгоритмы


  1. BC-дерево некоторого графа имеет радиус 2 и содержит 8 вершин, 4 из которых являются листьями. Сколько шарниров у этого графа?

  2. G и H - графы с одним и тем же множеством вершин. В графе G 8 ребер, в графе H 9 ребер, а в графе G \cup H 12 ребер. Сколько ребер в графе G \oplus H ?

  3. Алгоритм поиска в глубину применяется к лесу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

  4. Алгоритм поиска в глубину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

  5. Алгоритм поиска в глубину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

  6. Алгоритм поиска в ширину применяется к дереву, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

  7. Алгоритм поиска в ширину применяется к планарному графу, заданному матрицей смежности. Какие оценки трудоемкости справедливы в этом случае?

  8. Алгоритм поиска в ширину применяется к планарному графу, заданному списками смежности. Какие оценки трудоемкости справедливы в этом случае?

  9. В графе 6 вершин и 8 ребер. Сколько единиц будет в матрице инцидентности дополнительного графа?

  10. В графе K5 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?

  11. В графе K6 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет вес дерева, построенного для этого графа с помощью алгоритма Дейкстры?

  12. В графе K7 все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 5. Каков будет степень корня у дерева, построенного для этого графа с помощью алгоритма Дейкстры?

  13. В графе с 10 вершинами вес каждого ребра равен 1 или 2, причем ребра веса 2 порождают остовный подграф с тремя компонентами связности. Чему равен вес оптимального каркаса для этого графа?

  14. В графе с 10 вершинами существует гамильтонов цикл, все ребра которого имеют вес 1. Имеются еще два ребра веса 2, не принадлежащие циклу. Других ребер в графе нет. Каков будет вес оптимального каркаса для этого графа?

  15. В графе с весовой функцией w строится каркас с помощью алгоритма Краскала. Пусть e_1 ,e_2 , \ldots ,e_k - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого i = 2,3, \ldots k?

  16. В графе с весовой функцией w строится каркас с помощью алгоритма Прима. Пусть e_1 ,e_2 , \ldots ,e_k - список всех ребер каркаса в том порядке, в каком они добавлялись при построении.
    Какие из следующих утверждений верны для любого графа, любой весовой функции и любого i = 2,3, \ldots k?

  17. В двудольном графе одна доля состоит из пяти вершин степени 2, а другая из трех вершин, две из которых имеют степень 3. Какова степень третьей вершины?

  18. В дереве имеется ровно три листа a,b,c, причем d(a,b) = 8, d(a,c) = 9, d(b,c) = 5. Сколько всего вершин в этом дереве?

  19. В каких из следующих графов имеется гамильтонов цикл?

  20. В каких из следующих случаев можно утверждать, что путь, соединяющий вершины x и y в BFS-дереве, является кратчайшим путем между ними в графе?

  21. В планарном графе семь вершин, из которых три имеют степень 4, остальные степень 5. Сколько граней будет в плоском изображении этого графа?

  22. В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим и имеет пропускную способность 1. Какова наибольшая величина потока от вершины 1 к вершине 6?

  23. В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

  24. В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро (i,j), i j, имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?

  25. В процессе выполнения процедуры поиска в ширину вершины графа делятся на новые, открытые и закрытые. Может ли в графе существовать ребро, соединяющее

  26. В связном взвешенном графе для каждой вершины выбрано одно инцидентное ей ребро наибольшего веса. Какие из следующих утверждений верны?

  27. Граф G имеет 4 вершины, а в его матрице смежности 8 единиц. Граф H имеет 5 вершин, а в его матрице смежности 12 единиц. Сколько единиц будет в матрице смежности графа G \circ H ?

  28. Дан граф G с множеством вершин V, \Phi - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара (V,\Phi ) является матроидом,?

  29. Дан граф G с множеством ребер E. Для каких из перечисленных ниже семейств \Phi подмножеств множества E пара (E,\Phi ) является матроидом для любого графа G?

  30. Дано непустое конечное множество E и семейство его подмножеств \Phi . В каких из перечисленных ниже случаев пара (E,\Phi ) является матроидом?

  31. Дерево имеет две центральные вершины, а его радиус равен 6. Чему равен диаметр этого дерева?

  32. Для двудольного графа построено BFS-дерево с корнем a . Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?

  33. Для двудольного графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

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

  35. Для каких из перечисленных графов задача о раскраске может быть решена с помощью одних сжатий по включению?

  36. Для некоторого графа построено BFS-дерево с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в графе)?

  37. Для некоторого графа построено DFS-дерево T с корнем a. Ребро графа (x,y) дереву не принадлежит. Какие из следующих соотношений могут выполняться (d обозначает расстояние между вершинами в дереве T)?

  38. Для некоторого графа построено DFS-дерево и вычислены глубинные номера вершин. Какие из следующих утверждений верны?

  39. Для некоторого графа с заданным в нем паросочетанием построено дерево достижимости T с корнем в свободной вершине a. Какие из следующих утверждений верны для любого графа, любого паросочетания и любого дерева достижимости?

  40. К графу 2C5 применяется описанный в лекции 11 алгоритм решения задачи о независимом множестве со сжатием по включению. Сколько листьев будет в возникающем при этом дереве подзадач?

  41. Как может измениться цикломатическое число при добавлении к графу нового ребра?

  42. Какие из следующих графов изоморфны графу\overline {C_5 }?

  43. Какие из следующих графов планарны?

  44. Какие из следующих графов являются двудольными?

  45. Какие из следующих операций сохраняют свойство хордальности, т. е. при применении операции к хордальному графу всегда получается хордальный граф?

  46. Какие из следующих равенств выполняются для любых графов G, H и F с одним и тем же множеством вершин

  47. Какие из следующих равенств выполняются для любых графов G1 и G2?

  48. Какие из следующих равенств выполняются для любых графов G1 и G2?

  49. Какие из следующих равенств выполняются для любых графов G1 и G2?

  50. Какие из следующих равенств выполняются для любых графов G1 и G2?

  51. Какие из следующих условий являются необходимыми и достаточными для того, чтобы граф имел хроматический индекс 2?

  52. Какие из следующих утверждений верны для любого взвешенного графа?

  53. Какие из следующих утверждений верны для любого графаG и любого его подграфаH?

  54. Какие из следующих утверждений верны для системы фундаментальных циклов, построенной относительно некоторого каркаса?

  55. Какие из следующих утверждений верны?

  56. Какие из следующих утверждений верны?

  57. Какие из следующих утверждений верны?

  58. Какие из следующих утверждений верны?

  59. Какие из следующих утверждений верны?

  60. Какие из следующих утверждений верны?

  61. Какие из следующих утверждений верны?

  62. Какие из следующих утверждений верны?

  63. Какие из следующих утверждений верны?

  64. Какие из следующих утверждений справедливы для любого двусвязного графа?

  65. Какова будет наибольшая из длин фундаментальных циклов относительно каркаса, построенного с помощью поиска в глубину для графа K3,5?

  66. Какова будет суммарная длина фундаментальных циклов относительно каркаса, построенного с помощью поиска в ширину для графа K7 ?

  67. Какое наименьшее количество новых ребер нужно добавить к графу C6, чтобы получился непланарный граф?

  68. Какое наименьшее число ребер нужно добавить к графу K3,3, чтобы превратить его в хордальный?

  69. Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?

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

  71. Какое наименьшее число ребер нужно удалить из графа K6, чтобы получился планарный граф?

  72. Какое наименьшее число ребер нужно удалить из графа K8 , чтобы получился граф, в котором есть эйлеров цикл?

  73. Какое наименьшее число ребер нужно удалить из графа P_3 \times P_3 , чтобы превратить его в хордальный?

  74. Каркасы, построенные для некоторого графа с помощью алгоритмов Прима, Крускала и Дейкстры, имеют соответственно веса a, b и c. Какое из следующих соотношений обязательно выполняются для этих чисел?

  75. Корневое дерево имеет радиус 4, а у каждой его вершины не более двух сыновей. Каково наибольшее число вершин в таком дереве?

  76. Поиск в глубину применяется к графу K_2 \times O_4 . Какова будет высота DFS-дерева?

  77. Поиск в ширину применяется к графу P_3 \times P_3 . Какой будет высота BFS-дерева?

  78. Пусть (E,\Phi ) - матроид и на множестве E задана весовая функция w с вещественными значениями. Что произойдет, если к нему применить алгоритм СПО, в котором на первом этапе элементы множества E упорядочиваются не по убыванию, а по возрастанию весов?

  79. Пусть e_1 ,e_2 , \ldots ,e_m - список ребер графа в порядке убывания весов. Какие из следующих утверждений верны для любого графа и любой весовой функции?

  80. Пусть e_1 и e_2 - ребра с наименьшими весами в некотором взвешенном графе, причем w(e_1 ) \le w(e_2 ). Какие из следующих утверждений верны для любого графа и любой весовой функции?

  81. Пусть h - высота BFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

  82. Пусть h - высота DFS-дерева, построенного для графа G. Какие из следующих утверждений верны?

  83. Пусть каждая из функций f_1 и f_2 является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?

  84. Сколько имеется абстрактных графов с 4 вершинами диаметра 2?

  85. Сколько имеется абстрактных графов с 4 вершинами радиуса 1?

  86. Сколько имеется абстрактных графов с 4 вершинами, у которых центр состоит ровно из 2 вершин?

  87. Сколько имеется абстрактных графов с 5 вершинами, не являющихся хордальными?

  88. Сколько имеется абстрактных двудольных графов с 4 вершинами?

  89. Сколько имеется абстрактных двусвязных графов с 4 вершинами?

  90. Сколько имеется абстрактных деревьев с 6 вершинами?

  91. Сколько имеется абстрактных обыкновенных графов с 4 вершинами и 3 ребрами?

  92. Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?

  93. Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 4, 4, 5, 5)?

  94. Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?

  95. Сколько имеется абстрактных обыкновенных графов с набором степеней (3, 3, 3, 3, 4, 4)?

  96. Сколько имеется абстрактных ориентированных графов без петель и кратных ребер с 3 вершинами и 3 ребрами?

  97. Сколько имеется неориентированных графов, в которых допускаются петли, но не кратные ребра, с множеством вершин {1, 2, 3}?

  98. Сколько имеется ориентированных графов без петель и кратных ребер с множеством вершин {1, 2, 3}?

  99. Сколько имеется связных абстрактных графов с 4 вершинами?

  100. Сколько имеется связных абстрактных графов с 5 вершинами, в которых существует эйлеров цикл?

  101. Сколько листьев будет в дереве вариантов при применении описанного в лекции 10 переборного алгоритма раскраски вершин к графу C4 ?

  102. Сколько листьев будет в дереве подзадач для задачи о независимом множестве, построенном для графа 3K3?

  103. Сколько листьев будет в дереве путей, построенном для графа K4,4?

  104. Сколько максимальных независимых множеств имеется у графа P5?

  105. Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу C_{12}?

  106. Сколько различных каркасов имеется у графа K_4 ?

  107. Сколько различных наибольших паросочетаний имеется в графе K_5?

  108. Сколько ребер имеет граф пересечений граней трехмерного куба?

  109. Сколько ребер нужно добавить к наибольшему паросочетанию графа K_{2,5} + C_9, чтобы получить наименьшее реберное покрытие этого графа?

  110. Сколько ребер нужно удалить из наименьшего реберного покрытия графа K_{4,6} + K_7 , чтобы получить наибольшее паросочетание этого графа?

  111. Сколько существует абстрактных связных графов с 5 вершинами, имеющих ровно два блока?

  112. Чему равно кликовое число графа C9?

  113. Чему равно хроматическое число графа C_3 \circ C_4 ?

  114. Чему равно число вершинного покрытия графа P_3 \times P_4 ?

  115. Чему равно число независимости графа Q3?

  116. Чему равны хроматические индексы графов K3,3 и C7 ?

  117. Что получится, если к графу P_3 \times P_3 применить каждый из двух описанных в лекции 9 эвристических алгоритмов для задачи о независимом множестве: 1) удаление вершины наибольшей степени на каждом шаге; 2) удаление окрестности вершины наименьшей степени на каждом шаге?

  118. Что произойдет, если алгоритм СПО применить к матроиду, на множестве элементов которого задана весовая функция с произвольными вещественными значениями (могут быть и отрицательные веса).

  119. Что произойдет, если описанный в лекции 8 алгоритм построения эйлерова цикла применить к графу Pn(без предварительной проверки четности степеней)?

  120. Что происходит с диаметром графа при удалении вершины?

  121. Что происходит с диаметром графа при удалении ребра?

  122. Что происходит с радиусом графа при добавлении нового ребра?

  123. Что происходит с хроматическим числом графа при удалении ребра?


Актуальная информация по учебным программам ИНТУИТ расположена по адресу: http://www.intuit.ru/.

Повышение квалификации

(программ: 450)

Профессиональная переподготовка

(программ: 14)

Лицензия на образовательную деятельность и приложение











Developer Project предлагает поддержку при сдаче экзаменов учебных курсов Интернет-университета информационных технологий INTUIT (ИНТУИТ). Мы ответили на экзаменационные вопросы 380 курсов INTUIT (ИНТУИТ), всего 110 300 вопросов, 154 221 ответов (некоторые вопросы курсов INTUIT имеют несколько правильных ответов). Текущий каталог ответов на экзаменационные вопросы курсов ИНТУИТ опубликован на сайте объединения Developer Project по адресу: http://www.dp5.su/

Подтверждения правильности ответов можно найти в разделе «ГАЛЕРЕЯ», верхнее меню, там опубликованы результаты сдачи экзаменов по 100 курсам (удостоверения, сертификаты и приложения с оценками).

Более 21 000 вопросов по 70 курсам и ответы на них, опубликованы на сайте http://www.dp5.su/, и доступны зарегистрированным пользователям. По остальным экзаменационным вопросам курсов ИНТУИТ мы оказываем платные услуги (см. вкладку верхнего меню «ЗАКАЗАТЬ УСЛУГУ». Условия поддержки и помощи при сдаче экзаменов по учебным программам ИНТУИТ опубликованы по адресу: http://www.dp5.su/

Примечания:

- ошибки в текстах вопросов являются оригинальными (ошибки ИНТУИТ) и не исправляются нами по следующей причине - ответы легче подбирать на вопросы со специфическими ошибками в текстах;

- часть вопросов могла не войти в настоящий перечень, т.к. они представлены в графической форме. В перечне возможны неточности формулировок вопросов, что связано с дефектами распознавания графики, а так же коррекцией со стороны разработчиков курсов.


Похожие:

Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit) : Графы и их применение
Граф g состоит из k компонент. Что нужно сделать, чтобы из заданного графа получить остовной лес?
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 341. Вычислительная математика и структура алгоритмов Алгоритмы сдваивания применяются для
В графе метода Жордана рассылка элементов u j осуществляется вдоль прямых, параллельных
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit) : Комбинаторные алгоритмы для программистов
В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства...
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 350. Языки и исчисления "Сколемовская нормальная форма"
Бескванторная формула сигнатуры s = \left\langle { =,,0,1, +,x} \right\rangle
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 217. Основы информатики и программирования
Большинство предикатов в состоянии, в котором не определены некоторые из переменных, входящих в него
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit): Алгоритмические основы современной компьютерной графики
Благодаря чему достигается быстрота алгоритма Брезенхема разложения отрезка в растр?
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconОтветы на экзаменационные вопросы интернет-курсов интуит (intuit): 294. Программирование на языке C++
В условном операторе между ключевыми словами if и else после выражения в скобках может находиться
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconОтветы на экзаменационные вопросы интернет-курсов интуит (intuit): 154. Введение в компьютерную алгебру
Согласно алгоритму Кронекера, коэффициенты многочлена f1 однозначно восстанавливаются по его значениям
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit): Криптографические основы безопасности
В уравнениях эллиптических кривых бесконечно удаленная точка, в которой сходятся все вертикальные прямые, называется
Экзаменационные вопросы интернет-курсов интуит (intuit) : Графы и алгоритмы iconЭкзаменационные вопросы интернет-курсов интуит (intuit): 346. Основы теории вычислимых функций
Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org