1 Выполнен Баллов: 1,00 из 1,00 Отметить вопрос Текст вопроса Алгоритм поиска в глубину позволяет построить обход ориентированного или неориентированного графа, при котором посещаются доступные из начальной вершины Выберите один ответ

Разделяй и властвуй 
o
Метод заворачивания подарка (метод Джарвиса) 
92. 
Какой метод относятся к «Методу грубой силы» 

Распознавание ребер оболочки 
o
Инкрементальный алгоритм 
o
Разделяй и властвуй 
o
Метод заворачивания подарка (метод Джарвиса) 
93. 
Какой метод относятся к «Методу пошагового ввода» 
o
Распознавание ребер оболочки 

---


Инкрементальный алгоритм 
o
Разделяй и властвуй 
o
Метод заворачивания подарка (метод Джарвиса) 
94. 
Какой метод относятся к «Методу декомпозиции» 
o
Распознавание ребер оболочки 
o
Инкрементальный алгоритм 

Разделяй и властвуй 
o
Метод заворачивания подарка (метод Джарвиса) 
95. 
Какой метод относятся к «Методу пошаговой выборки» 
o
Распознавание ребер оболочки 
o
Инкрементальный алгоритм 
o
Разделяй и властвуй 

Метод заворачивания подарка (метод Джарвиса) 
96. 
На каком алгоритме основана Триангуляция Делоне 

Алгоритм «разделяй и властвуй» 
o
Алгоритм «ветвей и границ» 
o
Алгоритм Дейкстра 
o
Алгоритм Прима 
97. 
Триангуляция Делоне обладает… 

максимальной суммой минимальных углов всех треугольников среди всех возможных 
триангуляций 
o
минимальной суммой максимальных углов всех треугольников среди всех возможных 
триангуляций 
o
минимальной суммой минимальных углов всех треугольников среди всех возможных 
триангуляций 
o
максимальной суммой радиусов окружностей, описанных около треугольников, среди всех 
возможных триангуляций 
98. 
Триангуляция Делоне обладает… 

минимальной суммой радиусов окружностей, описанных около треугольников, среди всех 
возможных триангуляций 
o
минимальной суммой максимальных углов всех треугольников среди всех возможных 
триангуляций 
o
минимальной суммой минимальных углов всех треугольников среди всех возможных 
триангуляций 
o
максимальной суммой радиусов окружностей, описанных около треугольников, среди всех 
возможных триангуляций 
99. 
В чьих трудах впервые встречается первое использование диаграммы Воронова? 

Рене Декарт (1644) 
o
Иоганн Петер Густав Лежён-Дирихле (1908) 
o
Георгий Феодосьевич Вороной (1908) 

---

o
Борис Николаевич Делоне (1953) 
100. 
Первое использование этой диаграммы встречается в труде Рене Декарта «Начала 
философии» (1644). 

Диаграмма Воронова 
o
Диаграммы для двух- и трехмерного случаев 
o
Диаграмма Венна 
o
Диаграмма Гаусса 
101. 
Какие графы называются неориентированными? 

Графы, в которых все рёбра являются звеньями (порядок двух концов ребра графа не 
существенен) 
o
Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа 
существенен) 
o
Графы, содержащие только взвешенные рёбра 
o
Только классические графы 
102. 
Какие графы называются ориентированными? 
o
Графы, в которых все рёбра являются звеньями (порядок двух концов ребра графа не 
существенен) 

Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа 
существенен) 
o
Графы, содержащие только взвешенные рёбра 
o
Только классические графы 
103. 
Как называется алгоритм нахождения кратчайших путей из одного источника? 

Алгоритм Дейкстры 
o
Алгоритм Крускала 
o
Алгоритм Прима 
o
Алгоритм Призма 
104. 
Как называется алгоритм построения минимального остова графа? 
o
Алгоритм Дейкстры 

Алгоритм Крускала 
o
Алгоритм Прима 
o
Алгоритм Призма 
105. 
Как называется алгоритм ближайшего соседа? 
o
Алгоритм Дейкстры 
o
Алгоритм Крускала 

Алгоритм Прима 
o
Алгоритм Призма 
106. 
Признаки того, что задачу возможно решить при помощи жадного алгоритма: 
o
Задачу можно разбить на подзадачи; 
o
Величины, рассматриваемые в задаче, можно дробить так же на подзадачи; 

---

o
Сумма оптимальных решений для двух подзадач даст оптимальное решения для всей 
задачи. 

Все ответы верны 
107. 
Принцип жадного выбора: 

к задаче оптимизации применим принцип жадного выбора, если последовательность 
локально оптимальных выборов ДАЁТ глобально оптимальное решение 
o
к задаче оптимизации применим принцип жадного выбора, если последовательность 
локально оптимальных выборов НЕ ДАЁТ глобально оптимальное решение 
o
к задаче оптимизации применим принцип жадного выбора, если последовательность 
локально оптимальных выборов ВООБЩЕ НЕ ДАЁТ никакое решение 
o
к задаче оптимизации применим принцип жадного выбора, если последовательность 
локально оптимальных выборов ДАЁТ ЛЮБОЕ решение 
108. 
Отличительная особенность «жадного алгоритма»: 

Последовательность локально оптимальных выборов дает глобально оптимальное решение 
o
Алгоритм на каждом шаге выбирает множество, покрывающее максимальное число все еще 
непокрытых элементов 
o
На каждом шаге выбирается вершина максимальной степени и выкидывается из графа все 
покрытые ребра 
o
Предполагает такую декомпозицию (разбиение) задачи размера на более мелкие задачи, 
что на основе решений этих более мелких задач можно легко получить решение исходной 
задачи 
109. 
Принцип жадного выбора: 

Последовательность локально оптимальных выборов дает глобально оптимальное решение 
o
Алгоритм на каждом шаге выбирает множество, покрывающее максимальное число все еще 
непокрытых элементов 
o
На каждом шаге выбирается вершина максимальной степени и выкидывается из графа все 
покрытые ребра 
o
Предполагает такую декомпозицию (разбиение) задачи размера п на более мелкие задачи, 
что на основе решений этих более мелких задач можно легко получить решение исходной 
задачи 
110. 
Свойство оптимальности для подзадач: 

Оптимальное решение для задачи содержит оптимальные решения для подзадач 
o
Алгоритм на каждом шаге выбирает множество, покрывающее максимальное число все еще 
непокрытых элементов 
o
На каждом шаге выбирается вершина максимальной степени и выкидывается из графа все 
покрытые ребра 
o
Предполагает такую декомпозицию (разбиение) задачи размера п на более мелкие задачи, 
что на основе решений этих более мелких задач можно легко получить решение исходной 
задачи 
111. 
Когда возникла комбинаторика? 

В XVI веке 
o
В XXI 
o
В XX веке 
o
В XV веке 

---

112. 
Множество – это… 

набор элементов одинакового типа, которые рассматриваются как единое целое 
o
совокупность объектов, над которыми выполняют операции 
o
языковая конструкция для вычисления значения с помощью одного или нескольких 
операндов 
o
подмножество с определенными свойствами из элементов конкретного множества 
113. 
Множество – это… 

совокупность объектов любой природы, обладающих некоторым общим свойством 
o
совокупность объектов, над которыми выполняют операции 
o
языковая конструкция для вычисления значения с помощью одного или нескольких 
операндов 
o
подмножество с определенными свойствами из элементов конкретного множества 
114. 
Совокупность объектов любой природы, обладающих некоторым общим свойством 
– это… 

Множество 
o
Величина 
o
Объект 
o
Алгоритм 
115. 
Объекты, объединенные общим свойством, называются…

элементами множества 
o
элементами величины 
o
элементами объекта 
o
элементами алгоритма 
116. 
При обозначении множеств используют: 
o
только круглые скобки 

только фигурные скобки 
o
иногда круглые, иногда фигурные, иногда одновременно оба вида скобок 
o
вообще не используют скобки 
117. 
При операциях на числовых множествах за универсальное множество берут: 
o
все целые числа 
o
только множество натуральных чисел 

всё множество действительных чисел 
o
множество любых чисел 
118. 
Как можно изобразить множество графически: 
o