[Росдистант] Дискретная математика и математическая кибернетика (тесты, вопросы, ответы)
Тольяттинский государственный университет (Росдистант), ТГУ. Дискретная математика и математическая кибернетика (8840, 9657). Итоговый тест. Ответы на вопросы.
Для Росдистант имеются и другие готовые работы. Пишем уникальные работы под заказ. Помогаем с прохождением онлайн-тестов. Пишите, пожалуйста, в личку (Евгений).
ИТОГОВЫЙ ТЕСТ (в базе более 50 вопросов)
Пусть применяется алгоритм Дейкстра для поиска минимальных путей от вершины a, т.е. на первой итерации алгоритма вершина a является текущей. Выберите текущую вершину на третьей итерации.
Выберите один ответ:
f
c
d
e
b
Сопоставьте маршруты в данном графе с их названиями. Используйте каждый термин не более чем один раз.
adghdce
adghec
dghdced
gadghdg
Выберите...
цепь
замкнутый маршрут
цикл
простая цепь
Сопоставьте элементарным функциям двойственные им функции.
Штрих Шеффера
Эквивалентность
Конъюнкция
Тождественная функция
Выберите...
Тождественная функция
Константа 1
Сумма по модулю два
Инверсия
Стрелка Пирса
Дизъюнкция
Какой граф изоморфен данному?
Выберите один ответ:
Какую ДНФ можно считать приближенной кратчайшей?
Выберите один или несколько ответов:
Любую ДНФ, достаточно близкую по длине к кратчайшей.
ДНФ не бывает приближенной кратчайшей.
Безызбыточную ДНФ.
Выделите вершины с номером волны 2 в волновом алгоритме, если a – стартовая вершина
Выберите один или несколько ответов:
a
e
c
b
g
f
h
d
i
Сколько безызбыточных ДНФ у булевой функции?
Ответ:
Какое из следующих утверждений верно для любого простого графа с более чем двумя вершинами?
Выберите один ответ:
По меньшей мере три вершины имеют одинаковые степени.
Все вершины имеют одинаковые степени.
По меньшей мере две вершины имеют одинаковые степени.
Не существует двух вершин с одинаковой степенью.
Какое ребро должно проходиться повторно в оптимальном маршруте почтальона?
Выберите один ответ:
ad
ab
ae
Перечислите по порядку шаги алгоритма поиска одного кратчайшего покрытия.
Составление КНФ функции покрытия циклического остатка
Ответ 1
Выберите...
5
1
3
6
2
4
Поиск однострочного покрытия
Ответ 2
Выберите...
5
1
3
6
2
4
Поиск ядерных строк
Ответ 3
Выберите...
5
1
3
6
2
4
Преобразование КНФ в ДНФ
Ответ 4
Выберите...
5
1
3
6
2
4
Поиск столбцов-последователей
Ответ 5
Выберите...
5
1
3
6
2
4
Поиск строк-предшественниц
Ответ 6
Выберите...
5
1
3
6
2
4
Совместите названия объектов с их диаграммами
Выберите...
Эйлеров орграф
Эйлеров граф
Полуэйлеров граф
Полуэйлеров орграф
Какой гамильтонов цикл можно получить в результате работы алгоритма Эйлера?
Выберите один ответ:
acebda
adceba
abcdea
Ранг элементарной конъюнкции - это...
Выберите один ответ:
число переменных в конъюнкции.
число переменных в пространстве переменных.
число переменных, входящих в конъюнкцию без инверсии.
число переменных, входящих в конъюнкцию с инверсией.
Выберите для данного графа верные утверждения
Выберите один или несколько ответов:
Точек сочленения нет
Ребро y – мост
Вершина a – точка сочленения
Вершина b – точка сочленения
Какие утверждения верны для данного графа?
Выберите один или несколько ответов:
Ребра a и b не смежны
Вершины a и d смежны
Ребро t инцидентно вершине f
Вершина d является изолированной
Отметьте верные утверждения
Выберите один или несколько ответов:
Все ДНФ кратчайшей системы ДНФ должны быть простыми кратчайшими.
Понятия «кратчайшая система ДНФ» и «система кратчайших ДНФ» не являются эквивалентными.
Система безызбыточных ДНФ является также и безызбыточной системой ДНФ.
Безызбыточная система ДНФ всегда состоит из безызбыточных ДНФ.
Каково максимальное число ребер в графе с шестью вершинами и двумя компонентами связности?
Ответ:
Постройте кратчайшую систему ДНФ для данной системы функций и запишите ее длину.
Ответ:
Пусть после нескольких шагов алгоритма Флери построен маршрут abedaf. Выберите верное утверждение.
Выберите один ответ:
Далее можно перейти в вершину c и стереть ребро fc.
Такой маршрут не может быть построен алгоритмом Флери.
Далее можно перейти в вершину e и стереть ребро fe.
Пусть применяется модификация алгоритма Дейкстра для поиска минимальных путей от вершины a. В таблице приведены две первые итерации алгоритма.
Сопоставьте вершинам веса минимальных путей от вершины
aa
на третьей итерации.
b
Выберите...
0
3
6
4
2
5
a
Выберите...
0
3
6
4
2
5
d
Выберите...
0
3
6
4
2
5
c
Выберите...
0
3
6
4
2
5
Пусть после нескольких шагов алгоритма Робертса и Флореса получен маршрут abe. Выберите верное утверждения.
Выберите один ответ:
Можно добавить вершину a в конец маршрута.
Можно добавить вершину b в конец маршрута.
Можно добавить вершину d в конец маршрута.
Совместите названия объектов с диаграммами. Используйте каждое определение один раз.
Выберите...
Плоский граф
Непланарный граф
Планарный граф
Выберите...
Плоский граф
Непланарный граф
Планарный граф
Выберите...
Плоский граф
Непланарный граф
Планарный граф
Сколько сегментов имеет данный граф (слева) относительно его частичной укладки (справа)?
Ответ:
Запишите минимальный путь <a, c> (маленькими латинскими буквами, без пробелов и знаков препинания).
Ответ:
Для данного графа выполнялся алгоритм Флойда последовательно для вершин {a,b,c,d}.
После первой итерации алгоритма матрицы
и
HH
имеют вид:
Запишите элементы матрицы
после второй итерации.
Lambda (a, c)
Выберите...
3
5
0
7
4
-2
Lambda (a, d)
Выберите...
3
5
0
7
4
-2
Lambda (d, d)
Выберите...
3
5
0
7
4
-2
Какие матрицы смежности соответствуют данной матрице инциденций (нули в матрицах опущены)?
Выберите один ответ:
Отметьте верные утверждения.
Выберите один или несколько ответов:
Алгоритм Блейка-Порецкого строит сокращенную ДНФ функции только по ее совершенной ДНФ.
Алгоритм Квайна-МакКласки строит сокращенную ДНФ функции по ее произвольной ДНФ.
Алгоритм Квайна-МакКласки строит сокращенную ДНФ функции только по ее совершенной ДНФ.
Алгоритм Блейка-Порецкого строит сокращенную ДНФ функции по ее произвольной ДНФ.
Для данного графа сопоставьте ребрам порядок их включения в кратчайший остов в алгоритме Краскала.
ac
Выберите...
2
не входит в кратчайший остов
6
5
3
be
Выберите...
2
не входит в кратчайший остов
6
5
3
bc
Выберите...
2
не входит в кратчайший остов
6
5
3
Вычислите значение максимального потока в данной сети.
Ответ:
Для данного графа выберите верные утверждения.
Выберите один или несколько ответов:
Вершина d – центр
Диаметр равен 4.
Максимальное удаление от вершины a равно 3.
Вершина b – центр
Запишите маршрут коммивояжера, полученный алгоритмом ближайшего соседа, если вершина b – стартовая (в формате bcdeab, без пробелов и запятых). Граф задан матрицей весов.
Ответ:
Сопоставьте вершинам веса минимальные пути от вершины a.
d
Выберите...
4
1
5
8
2
3
7
6
b
Выберите...
4
1
5
8
2
3
7
6
c
Выберите...
4
1
5
8
2
3
7
6
f
Выберите...
4
1
5
8
2
3
7
6
e
Выберите...
4
1
5
8
2
3
7
6
Выберите номера переменных, существенных для данной функции.
Выберите один или несколько ответов:
1
4
5
2
3
Сколько вершин у неориентированного графа с 27 ребрами, шестью вершинами степени 2, тремя вершинами степени 4, и остальными вершинами степени 3?
Ответ:
Какие формулы единственны для булевой функции?
Выберите один или несколько ответов:
Минимальная ДНФ
Кратчайшая ДНФ
Совершенная ДНФ
Совершенная КНФ
Безызбыточная ДНФ
Сокращенная ДНФ
Раскраска данного графа является минимальной.
Выберите один ответ:
верно
неверно
Выберите верные утверждения.
Выберите один или несколько ответов:
Любой граф без циклов – дерево.
Все вершины в дереве являются точками сочленения.
В дереве число ребер на единицу меньше числа вершин
Любое дерево не содержит мостов
Любое дерево не содержит циклов
Выберите из данных графов гамильтоновы.
Выберите один или несколько ответов:
Сопоставьте термины их определениям.
Покрытие таблицы Квайна, имеющее минимальную длину, называется
Покрытие таблицы Квайна, которое при удалении из него хотя бы одной строки перестает быть покрытием
Покрытие таблицы Квайна, имеющее минимальную сумму рангов строк
Выберите...
Кратчайшее покрытие
Безызбыточное покрытие
Минимальное покрытие
Сокращенное покрытие
Сопоставьте диаграммы с описывающими их терминами
Выберите...
Неориентированный мультиграф
Ориентированный мультиграф
Неориентированный мультипсевдограф
Ориентированный граф
Выберите...
Неориентированный мультиграф
Ориентированный мультиграф
Неориентированный мультипсевдограф
Ориентированный граф
Выберите...
Неориентированный мультиграф
Ориентированный мультиграф
Неориентированный мультипсевдограф
Ориентированный граф
Выберите...
Неориентированный мультиграф
Ориентированный мультиграф
Неориентированный мультипсевдограф
Ориентированный граф
Задано множество M = {1,2,3,4,5,6,7,8,9}. Представьте булевым вектором его подмножество четных чисел.
Ответ:
Целью минимизации булевой функции может являться...
Выберите один или несколько ответов:
построение сокращенной ДНФ.
построение совершенной ДНФ.
построение одной кратчайшей ДНФ.
построение всех минимальных ДНФ.
построение всех кратчайших ДНФ.
К данному графу применяется алгоритм раскраски Уэлша-Пауэлла. На данный момент 4 вершины окрашены. Каким может быть следующее действие?
Выберите один ответ:
Окрасить вершину a в фиолетовый цвет.
Завести новый цвет для вершины h.
Окрасить вершину d в фиолетовый цвет.
Окрасить вершину h в фиолетовый цвет.
Укажите этапы минимизации булевой функции.
Второй этап.
Первый этап.
Выберите...
Построение сокращенной ДНФ.
Построение совершенной ДНФ.
Построение произвольной ДНФ.
Построение кратчайшей ДНФ.
ля данного графа задача поиска минимальных путей не имеет решения.
Выберите один ответ:
неверно
верно
