|
Разделяй и властвуй
Метод Грэхема
152.
«Сканирующая линия» - это…
воображаемая прямая линия, которая в каждый момент сканирования делит набор точек на
3 части
o
воображаемая прямая линия, которая в каждый момент сканирования делит набор точек
пополам
o
реальная прямая линия, которая в каждый момент сканирования делит набор точек на 3
части
o
реальная прямая линия, которая в каждый момент сканирования делит набор точек пополам
153.
Воображаемая прямая линия, которая в каждый момент сканирования делит набор
точек на 3 части – это…
Сканирующая линия
o
Сканирующая прямая
o
Линия деления
o
Прямая деления
154.
На сколько частей в каждый момент сканирования делит набор точек
«Сканирующая линия»?
o
2
3
o
4
o
0
155.
Какие точки называются «Спящие точки»?
еще не обработанные точки
o
точки обрабатываемые в данный момент
o
уже обработанные точки
o
все точки на плоскости
156.
Какая диаграмма была описана для пространств больших размерностей?
Диаграмма Воронова
o
Диаграммы для двух- и трехмерного случаев
o
Диаграмма Венна
o
Диаграмма Гаусса
157.
Какие многоугольники используются в Диаграмме Воронова?
Простые многоугольники
o
Невыпуклые многоугольники
o
Выпуклые и невыпуклые многоугольники
o
Любые многоугольники
158.
Простой многоугольник — это…
это многоугольник без самопересечений
o
это многоугольник, в котором найдутся такие две вершины, что через них проводится
прямая, пересекающая данный многоугольник где-либо ещё, кроме ребра, соединяющего
эти вершины
o
это многоугольник, у которого продолжения сторон не пересекают других его сторон
o
любой многоугольник является простым
159.
Невыпуклый многоугольник — это…
o
это многоугольник без самопересечений
это многоугольник, в котором найдутся такие две вершины, что через них проводится
прямая, пересекающая данный многоугольник где-либо ещё, кроме ребра, соединяющего
эти вершины
o
это многоугольник, у которого продолжения сторон не пересекают других его сторон
o
любой многоугольник является невыпуклый
160.
Выпуклый многоугольник — это…
o
это многоугольник без самопересечений
o
это многоугольник, в котором найдутся такие две вершины, что через них проводится
прямая, пересекающая данный многоугольник где-либо ещё, кроме ребра, соединяющего
эти вершины
это многоугольник, у которого продолжения сторон не пересекают других его сторон
o
любой многоугольник является выпуклый
161.
Ненаправленная линия (без стрелки), соединяющая вершины графа – это…
Ребро
o
Путь
o
Цикл
o
Дуга
162.
Последовательность рёбер и/или дуг графа, такая, что конец одной дуги (ребра)
является началом другой дуги (ребра) – это…
Путь
o
Ребро
o
Цикл
o
Дуга
163.
Путь, в котором совпадают начальная и конечная вершины графа – это…
Цикл
o
Ребро
o
Путь
o
Дуга
164.
Направленная линия (со стрелкой), соединяющая вершины графа – это…
Дуга
o
Ребро
o
Путь
o
Цикл
165.
Как называется Граф без ребер?
Пустой
o
Нулевой
o
Взвешенный
o
Конечный
166.
Как еще называют метод «разделяй и властвуй»?
Метод декомпозиции
o
Метод сравнения
o
Метод поиска
o
Метод оптимального решения
167.
Как еще называют метод «разделяй и властвуй»?
Метод разбиения
o
Метод сравнения
o
Метод поиска
o
Метод оптимального решения
168.
Принцип метода «разделяй и властвуй»
o
Последовательность локально оптимальных выборов дает глобально оптимальное решение
o
Алгоритм на каждом шаге выбирает множество, покрывающее максимальное число все еще
непокрытых элементов
o
На каждом шаге выбирается вершина максимальной степени и выкидывается из графа все
покрытые ребра
Предполагает такую декомпозицию (разбиение) задачи размера на более мелкие задачи,
что на основе решений этих более мелких задач можно легко получить решение исходной
задачи
169.
Где применяется метод «разделяй и властвуй»?
в сортировке слиянием
o
в сортировке выбором
o
в шейкерной сортировке
o
в сортировке пузырьком
170.
Где применяется метод «разделяй и властвуй»?
в деревьях двоичного поиска
o
в графиках поиска
o
в табличном поиске
o
во всех видах поиска
171.
Множества обозначаются…
большими латинскими буквами А,B,С,D,…X,У,Z
o
малыми латинскими буквами а,b,с,d,…x,у.z
o
большими буквами кириллицы А,Б,В,Г,…Э,Ю,Я
o
малыми буквами кириллицы а,б,в,г,…э,ю,я
172.
Элементы множества обозначаются…
малыми латинскими буквами а,b,с,d,…x,у.z
o
большими латинскими буквами А,B,С,D,…X,У,Z
o
большими буквами кириллицы А,Б,В,Г,…Э,Ю,Я
o
малыми буквами кириллицы а,б,в,г,…э,ю,я
173.
Множество, не содержащее ни одного элемента, называется:
пустым
o
конечным
o
нулевым
o
полным
174.
Число всех подмножеств множества K={7,9,11,13,15,17,19} равно:
o
182
128
o
88
o
118
175.
Множество решений уравнения записывается:
o
{-2,3}
o
(2;-3)
{2,-3}
o
{-3,2}
176.
Какой операции над множествами соответствует выражение: “Элемент,
принадлежащий полученному множеству, принадлежит множеству А И множеству В.”:
пересечение множеств
o
перечисление множеств
o
дополнение множества
o
умножение множеств
177.
Какой операции над множествами соответствует выражение: “Элемент,
принадлежащий полученному множеству, принадлежит множеству А ИЛИ множеству
В.”:
o
пересечение множеств
o
перечисление множеств
объединение множеств
o
параллель множеств
178.
Если элемент x принадлежит множеству X, то записывают:
x
∈
Х
o
x | X
o
x
⊂
X
o
x + X
179.
Если множество А является подмножеством В, то записывают:
o
А | B
А
⊂
В
o
А
∈
B
o
x + X
180.
В чем состоит задача комбинаторики?
В подсчете числа подмножеств с определенными свойствами, выбранных из некоторого
множества.
o
В подсчете числа отдельных видов комбинаций
o
В объединении непересекающихся конечных множеств
o
В выборе подмножеств с определенными свойствами
181.
Из нижеперечисленных определений, найдите точное понятие свойства алгоритма
«понятность»:
Алгоритм должен содержать только те команды, которые входят в систему его команд
o
Процесс решения задачи, который должен быть разбит на последовательность отдельных
шагов
o
Любое действие, которое должно быть строго и недвусмысленно определено в каждом
случае
o
Каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения
182.
Из нижеперечисленных определений, найдите точное понятие свойства алгоритма
«детерминированность»:
Любое правило (команда) алгоритма должно быть строго и недвусмысленно определено, и
описано для каждого случая
o
Алгоритм должен содержать только те команды, которые входят в систему его команд
o
Процесс решения задачи, который должен быть разбит на последовательность отдельных
шагов
o
Каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения
183.
Детерминированность от латинского – это…
определенный, точный
o
Do'stlaringiz bilan baham: |
