SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov (Вопросы к экзамену с ответами в виде тестирования)
Описание файла
Файл "SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov" внутри архива находится в папке "Вопросы к экзамену с ответами в виде тестирования". Документ из архива "Вопросы к экзамену с ответами в виде тестирования", который расположен в категории "". Всё это находится в предмете "объектно-ориентированное программирование (ооп)" из 3 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "ооп" в общих файлах.
Онлайн просмотр документа "SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov"
Текст из документа "SAOD_2_kurs_Grafy_3-_treti_pyat_voprosov"
| 4728 | Если граф G=(V, E)содержит дугу в виде упорядоченной пары вершин (а, b), то (укажите 3 правильных ответов) Ответы: - это граф ориентированный - это граф неориентированный - узел а - начало дуги - узел b- начало дуги - узел b- конец дуги |
| 4729 | Если граф G=(V, E)содержит дугу в виде не упорядоченной пары вершин (а, b), то (укажите 4 (из 7) правильных ответов) Ответы: - это граф ориентированный - это граф неориентированный - только узел а (а не b)является началом дуги - можно говорить, что этот граф содержит как дугу ab, так и дугу ba - только узел b(а не а)является концом дуги - граф содержит путь из вершины aв вершину b - граф содержит простой путь из вершины aв вершину b |
| 4730 | Пусть орграф G=(V, E)имеет последовательность вершин v1, v2, ...,v15, для которой существуют дуги вида v1®v2, v2®v3, ..., vn-1®v15. Причем нет ни одной петли, а число узлов равно 15. Что можно утверждать о таком графе? (укажите 3 правильных ответов) Ответы: - Данный граф полносвязанный - Последовательность дуг v1®v2, v2®v3, ..., vn-1®v15 образует путь длиной 15. - Данный граф связанный - Последовательность дуг v1®v2, v2®v3, ..., vn-1®v15 образует путь длиной 14. - Последовательность дуг v1®v2, v2®v3, ..., vn-1®v15 образует простой путь. - Данный граф содержит цикл. |
| 4731 | Пусть дан связанный орграф G=(V, E),причем все дуги имеют неотрицательный вес.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использоватьдля решения следующей задачи: Требуется определить, достижима ли вершина у из вершины х. (укажите 3 правильных ответов) Ответы: - алгоритм Дейкстры - алгоритм получения сильносвязной компоненты на графе - алгоритм Прима - алгоритм Крускала - метод поиска в глубину - алгоритм нахождение минимального паросочитания на графе - алгоритм Уоршелла (алгоритм транзитивного замыкания) |
| 4732 | Пусть дан связанный орграф G=(V, E),причем все дуги имеют неотрицательный вес.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использоватьдля решения следующей задачи: Требуется определить, достижима ли вершина у из вершины х. (укажите 3 правильных ответов) Ответы: - алгоритм получения сильносвязной компоненты на графе - алгоритм Флойда - алгоритм Прима - алгоритм Крускала - алгоритм нахождения максимального покрытия графа - метод поиска в ширину (волновой метод) - алгоритм Уоршелла (алгоритм транзитивного замыкания) |
| 4733 | Пусть дан связанный орграф G=(V, E),причем все дуги имеют неотрицательный вес.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: Требуется определить кратчайшее расстояние от вершины х до вершины у. (укажите 2 правильных ответов) Ответы: - алгоритм Дейкстры - алгоритм Флойда - алгоритм Прима - алгоритм Крускала - метод поиска в глубину - метод поиска в ширину - алгоритм Уоршелла (алгоритм транзитивного замыкания) |
| 4734 | Пусть дан связанный не взвешенный (и непомеченный)орграф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: Требуется определить кратчайшее расстояние между вершинами х и у. (укажите 3 правильных ответов) Ответы: - алгоритм Дейкстры - алгоритм Флойда - алгоритм Прима - алгоритм Крускала - метод поиска в глубину - метод поиска в ширину (волновой метод) - алгоритм Уоршелла (алгоритм транзитивного замыкания) |
| 4735 | Пусть дан связанный орграф G=(V, E),не имеющий петель.Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: требуется определить, является ли граф циклическим (укажите 2 правильных ответов) Ответы: - алгоритм Дейкстры - алгоритм Флойда - алгоритм Прима - алгоритм Крускала - метод поиска в глубину - метод поиска в ширину - алгоритм Уоршелла (алгоритм транзитивного замыкания) |
| 4736 | Пусть дан связанный неориентированный граф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: Требуется определить, является ли граф ациклическим. (укажите 4 правильных ответов) Ответы: - алгоритм Дейкстры - алгоритм Флойда - алгоритм Прима (на основе контроля одного из свойств остовных деревьев минимальной стоимости) - алгоритм Крускала (на основе контроля одного из свойств остовных деревьев минимальной стоимости) - метод поиска в глубину - метод поиска в ширину (волновой метод) |
| 4737 | Пусть дан связанный неориентированный граф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: определить такой связанный подграф G=(V, E’), чтобы сумма весов дуг принадлежащих Е’, была бы минимальна. (укажите 2 правильных ответов) Ответы: - алгоритм нахождения максимального покрытия графа - алгоритм Флойда - алгоритм Прима - алгоритм Крускала - метод поиска в глубину - метод поиска в ширину - алгоритм нахождения минимального парасочитания |
| 4738 | Пусть дан связанный неориентированный граф G=(V, E).Отметьте те алгоритмы (полные варианты, возможно с некоторой адаптацией), которые можно использовать для решения следующей задачи: построить остовное дерево минимальной стоимости. (укажите 2 правильных ответов) Ответы: - алгоритм Дейкстры - алгоритм Флойда - алгоритм Прима - алгоритм Крускала - алгоритм нахождения минимального парасочитания - метод поиска в ширину (волновой метод) - алгоритм нахождения максимального покрытия графа |
| 4739 | Пусть дан граф, педставленый на рис.Укажите результаттопологической сортировки представленного графа (т.е. последовательность вершин после топологической сортировки). (укажите 4 правильных ответов) Ответы: - С1, С2, С3, С4, С5 - С1, С2, С4, С3, С5 - С2, С4, С1, С3, С5 - С5, С4, С3, С2, С1 - С5, С4, С2, С3, С1 - С2, С1, С3, С4, С5 - С1, С3, С5, С2, С4 |
| 4740 | Укажитесвойствасвободных деревьев (укажите 2 правильных ответов) Ответы: - Каждое свободное дерево с числом вершин n, n> 1, имеет в точности n- 1 ребер. - При добавлении в свободное дерево нового ребра образуется цикл. - Сумма весов ребер свободного дерева наименьшая на множестве ребер графа - Свободное дерево представляет собой дерево без корня, ориентированное к листьям - Каждое свободное дерево является полносвязаннным графом |
| 4741 | Связный граф, не имеющий точек сочленения, называется (является) … (укажите 2 правильных ответов) Ответы: - двусвязным - k-связным, причем k>= 2, если между любой парой вершин vиwсуществует не менее kразных путей (k> 1), таких, что, за исключением вершин vиw, ни одна из вершин, входящих в один путь, не входит ни в какой другой из этих путей. - покрытием графа G= (V, E) - свободным деревом - k-связным, причем k=1 - паросочетанием графаG= (V, E) |
| 4742 | Граф называетсяk-связным, если… (укажите 2 правильных ответов) Ответы: - удаление любых k- 1 вершин не приведет к расчленению графа. - представляет собой свободное дерево - существует не менее kразличных деревьев в глубинном остовном лесу, построенном методом поиска в глубину - существует не менее kразличных деревьев в глубинном остовном лесу, построенном методом поиска в ширину - существует ровно k-1 различных деревьев в глубинном остовном лесу, построенном методом поиска в глубину - существует не менее k-1 различных путей между двумя любыми вершинами uи v, такие что ни один узел, отличный от узлов uи v(начального и конечного узлов такого пути) не входит в два различных пути. |
