SAOD_2_kurs_Grafy_4-_chetvertye_pyat_voprosov (1021523)
Текст из файла
| 4743 | Остовным деревом графа G= (V, E)называется… (укажите 2 правильных ответов) Ответы: - свободное дерево, содержащее все вершины Vграфа G - подграф, содержащее все вершины Vграфа G - подграф, содержащее все дуги Eграфа G - дерево без корня, содержащее все вершины Vграфа G - ациклический подграф, содержащее все вершины Vграфа G |
| 4744 | Пусть дано следующее определение: «Пусть G= (V, Е)- связный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через Uподмножество множества вершин V. Если (и, v)- такое ребро наименьшей стоимости, что и ОUи vОV\U, тогда для графа Gсуществует _______________, содержащее ребро (и, v). » Укажите пропущенные слова.. Ответы: - остовное дерево минимальной стоимости - редуцированный подграф минимальной стоимости - максимальное покрытие графа G - минимальное покрытие графа G - минимальный гамильтонов цикл - гамильтонов цикл минимальной стоимости - эквивалентный граф минимальной стоимости |
| 4745 | Какому алгоритму соответствует следующий фрагмент: «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОUи vОV\ U, затем вершина vпереносится из множества V\ Uв множество U. Этот процесс продолжается до тех пор, пока множество Uне станет равным множеству V. » Ответы: - алгоритму Прима - алгоритму Крускала - алоритму Дейкстра - решение задачи коммивояжера - обходу графа методом поиска в глубину - обходу графа методом поиска в ширину - вычислению эксцентриситета графа |
| 4746 | Какому алгоритму соответствует следующий фрагмент: «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОVи vОV, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n- 1 (где n- число узлов графа)» Ответы: - алгоритму Прима - алгоритму Крускала - алгоритму Дейкстра - решение задачи коммивояжера - обходу графа методом поиска в глубину - обходу графа методом поиска в ширину - вычислению эксцентриситета графа |
| 4747 | Какому алгоритму соответствует следующий фрагмент: «На каждом шаге к множеству U добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества U. Когда множество Uбудет содержать все вершины орграфа, тогда вспомогательный массив будет содержать длины кратчайших путей от источника к каждой вершине.» Ответы: - алгоритму Прима - алгоритму Крускала - алгоритму Дейкстра - решение задачи коммивояжера - обходу графа методом поиска в глубину - обходу графа методом поиска в ширину - вычислению эксцентриситета графа |
| 4748 | Какому алгоритму соответствует следующий фрагмент: «На каждом шаге рассматриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Если дуга ведет к еще не посещенному узлу, то остальные еще не посещенные узлы, связанные дугой с текущим, помещаются в стек, а алгоритм переходит к рассмотрению аналогичным образом такого узла, помечая как посещенный. Если у текущего узла связанных не посещенных узлов нет, то из стека «выталкивается» верхний элемент и алгоритм переход к рассмотрению такого узла. Данный процесс продолжается до тех пор, пока в стеке содержится хотя бы один элемент.» Ответы: - алгоритму Прима - алгоритму Крускала - алгоритму Дейкстра - решение задачи коммивояжера - обходу графа методом поиска в глубину - обходу графа методом поиска в ширину - вычислению эксцентриситета графа |
| 4749 | Какому алгоритму соответствует следующий фрагмент: «На каждом шаге рассматриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Еще не посещенное узлы, связанные дугой с текущим, помечаются и помещаются в очередь. Для обработки следующего узла из очереди «извлекается» очередной узел и обрабатывается аналогичным образом. Данный процесс продолжается до тех пор, пока в очереди содержится хотя бы один элемент.» Ответы: - алгоритму Прима - алгоритму Крускала - алгоритму Дейкстра - решение задачи коммивояжера - обходу графа методом поиска в глубину - обходу графа методом поиска в ширину - вычислению эксцентриситета графа |
| 4750 | Укажите описание алгоритма, которое может являться фрагментом построения остовного дерева минимальной стоимости алгоритмом Прима. Ответы: - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОUи vОV\ U, затем вершина vпереносится из множества V\ Uв множество U. Этот процесс продолжается до тех пор, пока множество Uне станет равным множеству V. » - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОVи vОV, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n- 1 (где n- число узлов графа)» - «На каждом шаге к множеству U добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества U. Когда множество Uбудет содержать все вершины орграфа, тогда вспомогательный массив будет содержать длины кратчайших путей от источника к каждой вершине.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Если дуга ведет к еще не посещенному узлу, то остальные еще не посещенные узлы, связанные дугой с текущим, помещаются в стек, а алгоритм переходит к рассмотрению аналогичным образом такого узла, помечая как посещенный. Если у текущего узла связанных непосещенных узлов нет, то из стека «выталкивается» верхний элемент и алгоритм переход к рассмотрению такого узла. Данный процесс продолжается до тех пор, пока в стеке содержится хотя бы один элемент.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Еще не посещенное узлы, связанные дугой с текущим, помечаются и помещаются в очередь. Для обработки следующего узла из очереди «извлекается» очередной узел и обрабатывается аналогичным образом. Данный процесс продолжается до тех пор, пока в очереди содержится хотя бы один элемент.» |
| 4751 | Укажите описание алгоритма, которое может являться фрагментом построения оставного дерева минимальной стоимости алгоритмом Крускула. Ответы: - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОUи vОV\ U, затем вершина vпереносится из множества V\ Uв множество U. Этот процесс продолжается до тех пор, пока множество Uне станет равным множеству V. » - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОVи vОV, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n- 1 (где n- число узлов графа)» - «На каждом шаге к множеству U добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества U. Когда множество Uбудет содержать все вершины орграфа, тогда вспомогательный массив будет содержать длины кратчайших путей от источника к каждой вершине.» - «На каждом шаге рассматриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Если дуга ведет к еще не посещенному узлу, то остальные еще не посещенные узлы, связанные дугой с текущим, помещаются в стек, а алгоритм переходит к рассмотрению аналогичным образом такого узла, помечая как посещенный. Если у текущего узла связанных не посещенных узлов нет, то из стека «выталкивается» верхний элемент и алгоритм переход к рассмотрению такого узла. Данный процесс продолжается до тех пор, пока в стеке содержится хотя бы один элемент.» - «На каждом шаге рассматриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Еще не посещенное узлы, связанные дугой с текущим, помечаются и помещаются в очередь Для обработки следующего узла из очереди «извлекается» очередной узел и обрабатывается аналогичным образом. Данный процесс продолжается до тех пор, пока в очереди содержится хотя бы один элемент.» |
| 4752 | Укажите описание алгоритма, которое может являться фрагментом алгоритма Дейкстры. Ответы: - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОUи vОV\ U, затем вершина vпереносится из множества V\ Uв множество U. Этот процесс продолжается до тех пор, пока множество Uне станет равным множеству V. » - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОVи vОV, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n- 1 (где n- число узлов графа)» - «На каждом шаге к множеству U добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества U. Когда множество Uбудет содержать все вершины орграфа, тогда вспомогательный массив будет содержать длины кратчайших путей от источника к каждой вершине.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Если дуга ведет к еще не посещенному узлу, то остальные еще не посещенные узлы, связанные дугой с текущим, помещаются в стек, а алгоритм переходит к рассмотрению аналогичным образом такого узла, помечая как посещенный. Если у текущего узла связанных непосещенных узлов нет, то из стека «выталкивается» верхний элемент и алгоритм переход к рассмотрению такого узла. Данный процесс продолжается до тех пор, пока в стеке содержится хотя бы один элемент.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Еще не посещенное узлы, связанные дугой с текущим, помечаются и помещаются в очередь. Для обработки следующего узла из очереди «извлекается» очередной узел и обрабатывается аналогичным образом. Данный процесс продолжается до тех пор, пока в очереди содержится хотя бы один элемент.» |
| 4753 | Укажите описание алгоритма, которое может являться фрагментом алгоритма обхода методом поиска в глубину Ответы: - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОUи vОV\ U, затем вершина vпереносится из множества V\ Uв множество U. Этот процесс продолжается до тех пор, пока множество Uне станет равным множеству V. » - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОVи vОV, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n- 1 (где n- число узлов графа)» - «На каждом шаге к множеству U добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества U. Когда множество Uбудет содержать все вершины орграфа, тогда вспомогательный массив будет содержать длины кратчайших путей от источника к каждой вершине.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Если дуга ведет к еще не посещенному узлу, то остальные еще не посещенные узлы, связанные дугой с текущим, помещаются в стек, а алгоритм переходит к рассмотрению аналогичным образом такого узла, помечая как посещенный. Если у текущего узла связанных непосещенных узлов нет, то из стека «выталкивается» верхний элемент и алгоритм переход к рассмотрению такого узла. Данный процесс продолжается до тех пор, пока в стеке содержится хотя бы один элемент.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Еще не посещенное узлы, связанные дугой с текущим, помечаются и помещаются в очередь. Для обработки следующего узла из очереди «извлекается» очередной узел и обрабатывается аналогичным образом. Данный процесс продолжается до тех пор, пока в очереди содержится хотя бы один элемент.» |
| 4754 | Укажите описание алгоритма, которое может являться фрагментом алгоритма обхода методом поиска в ширину Ответы: - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОUи vОV\ U, затем вершина vпереносится из множества V\ Uв множество U. Этот процесс продолжается до тех пор, пока множество Uне станет равным множеству V. » - «На каждом шаге алгоритма находится ребро наименьшей стоимости (и, v)такое, что и ОVи vОV, и оно еще не принимало участие в алгоритме. После проверки того, что это ребро не образует цикл на подграфе, содержащем все узлы и отобранные к текущему моменту дуги, данное ребро добавляется к данному подмножеству дуг, образующих решение задачи. Этот процесс продолжается до тех пор, пока число отобранных дуг не станет равным n- 1 (где n- число узлов графа)» - «На каждом шаге к множеству U добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества U. Когда множество Uбудет содержать все вершины орграфа, тогда вспомогательный массив будет содержать длины кратчайших путей от источника к каждой вершине.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Если дуга ведет к еще не посещенному узлу, то остальные еще не посещенные узлы, связанные дугой с текущим, помещаются в стек, а алгоритм переходит к рассмотрению аналогичным образом такого узла, помечая как посещенный. Если у текущего узла связанных непосещенных узлов нет, то из стека «выталкивается» верхний элемент и алгоритм переход к рассмотрению такого узла. Данный процесс продолжается до тех пор, пока в стеке содержится хотя бы один элемент.» - «На каждом шаге рассмотриваются в лексикографическом порядке дуги, исходящие из текущей вершины. Еще не посещенное узлы, связанные дугой с текущим, помечаются и помещаются в очередь. Для обработки следующего узла из очереди «извлекается» очередной узел и обрабатывается аналогичным образом. Данный процесс продолжается до тех пор, пока в очереди содержится хотя бы один элемент.» |
| 4755 | Как называется вершина v, при удалении которой и всех ребер, инцидентных этой вершине v, связная компонента графа разбивается на две или несколько частей Ответы: - Точкой сочлененияграфа - Точкой k-связанности, k> 1 - Центром графа - Эксцентриситетом графа - Корнем графа - Корнем дерева обхода в ширину - Корнем дерева обхода в глубину |
| 4756 | Определите задачу, решение которой предполагаетиспользование алгоритма Крускала Ответы: - Оптимизация трафика в компьютерной сети путем нахождения кратчайшего расстояния между двумя компьютерами в компьютерной сети - Проектирование такой топологии сети типа «звезда», при которой обеспечивалась минимальный расход сетевого кабеля - Проектирование такой топологии связей между компьютерами в компьютерной сети, при которой обеспечивалась повышенная надежность соединений в следствие наличия избыточных каналов связи - Проектирование такой топологии связей между компьютерами в компьютерной сети, при которой обеспечивался минимальный расход сетевого кабеля без учета топологических особенностей местности - Проектирование топологии типа «кольцо», при которой обеспечивался минимальный расход сетевого кабеля |
| 4757 | Определите задачу, решение которой предполагаетиспользование алгоритма Прима Ответы: - Оптимизация трафика в компьютерной сети путем нахождения кратчайшего расстояния между двумя компьютерами в компьютерной сети - Проектирование такой топологии сети типа «звезда», при которой обеспечивалась минимальный расход сетевого кабеля - Проектирование такой топологии связей между компьютерами в компьютерной сети, при которой обеспечивалась повышенная надежность соединений в следствие наличия избыточных каналов - Проектирование такой топологии связей между компьютерами в компьютерной сети, при которой обеспечивался минимальный расход сетевого кабеля - Проектирование топологии типа «кольцо», при которой обеспечивался минимальный расход сетевого кабеля |
| 4758 | Классическая задача коммивояжера представляет собой Ответы: - нахождение маршрута из пункта А в пункт В, так чтобы длина пути была минимальной - нахождение маршрута из пункта А в пункт В, так чтобы посетить все «города» (узлы графа) и дважды не проходить ни по одной дороге (дуге графа) - нахождение такого маршрута обхода всех городов, начиная из пункта А и им заканчивая, чтобы дважды не проходить ни по одной дороге (дуге графа) и длина такого маршрута была бы минимальной - нахождение такого маршрута обхода всех городов, начиная из пункта А и им заканчивая, чтобы дважды не посетить один и тот же город (узел графа) и длина такого маршрута была бы минимальной - нахождение такого маршрута обхода всех городов, начиная из пункта А и им заканчивая, чтобы дважды не посетить ни один и тот же город (узел графа), и пройти в обязательном порядке по каждой дороге (дуге графа), соединяющие эти города |
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
