Раздел 4. Теория графов
1. Ребра называются смежными, если они
а) инцидентны одной и той же вершине
б) параллельны
в) являются кратными
2. Если две вершины соединены одной дугой, они называются
а) инцидентными
б) коинцидентными
в) смежными
3. Какие из графов являются подграфами данного графа G
а)
б)
в)
г)
-
Если любые две вершины графа можно соединить простой цепью, то граф называется:
а) связным;
б) несвязным;
в) деревом;
г) остовом.
5. Сколько вершин содержит гамильтонов цикл графа с 5 вершинами?
а) 5
б) 4
в) 6
6. Граф содержит 7 дуг. Его эйлеров цикл будет состоять из
а) 6 дуг
б) 7 дуг
в) 8 дуг
7. Эйлеров цикл
а) содержит каждое ребро только один раз;
б) содержит каждую вершину только один раз;
в) проходит через все вершины и ребра графа только один раз.
8. Гамильтонов цикл
а) содержит каждое ребро только один раз;
б) содержит каждую вершину только один раз;
в) проходит через все вершины и ребра графа только один раз.
9. В эйлеровом графе все вершины
а) четной степени;
б) нечетной степени.
10. В полуэйлеровом графе допускаются
а) 3 вершины нечетной степени;
б) 2 вершины нечетной степени;
в) 1 вершина нечетной степени.
11. Какой алгоритм определяет гамильтоновы циклы графа:
а) Гильберта-Мура;
б) Флери;
в) Робертса-Флореса;
г) Дейкстры.
12. Какой из циклов графа с множеством вершин {a,b,c,d,e,f} является гамильтоновым?
а) abeca
б) fbecdf
в) abecdfa
г) abcdfca
13. Какой граф является гамильтоновым:
а
)
б
)
в
)
14. В алгебраической форме представления графов аксиома о единичном элементе формулируется следующим образом:
а)
б)
в)
г)
15. В алгебраической форме представления графов имеет ли место свойство коммутативности относительно операции конкатенации для ориентированных графов?
а) да
б) нет.
16. Правило минимизации фрагмента графа:
а)
;
б)
;
в)
.
17. Какая из аксиом абстрактной математической решетки не содержится в АФПГ:
а) ассоциативность;
б) дистрибутивность;
в) аксиома о единичном элементе;
г) аксиома о нулевом элементе.
18. Задача коммивояжера решается при помощи:
а) алгоритма Гильберта-Мура;
б) метода ветвей и границ;
в) алгоритма Краскала;
г) метода динамического программирования.
19. Увеличение нижней границы стоимостей решений в левых узлах поддерева осуществляется за счет:
а) выбора в преобразованной матрице стоимостей нуля, который при замене его на бесконечность позволяет вычесть наибольшее суммарное количество из строки и столбца, на пересечении которых он находится;
б) вычитания из строк и столбцов матрицы после понижения ее порядка минимальных элементов.
20. Выбор в преобразованной матрице стоимостей нуля, который при замене его на бесконечность позволяет вычесть наибольшее суммарное количество из строки и столбца, на пересечении которых он находится, определяет увеличение нижней границы стоимостей решений
а) в левых узлах поддерева;
б) в правых узлах поддерева.
21. Вычитание из строк и столбцов матрицы после понижения ее порядка минимальных элементов определяет увеличение нижней границы стоимостей решений:
а) в левых узлах поддерева;
б) в правых узлах поддерева.
22. Увеличение нижней границы стоимостей решений в правых узлах поддерева осуществляется за счет:
а) выбора в преобразованной матрице стоимостей нуля, который при замене его на бесконечность позволяет вычесть наибольшее суммарное количество из строки и столбца, на пересечении которых он находится;
б) вычитания из строк и столбцов матрицы после понижения ее порядка минимальных элементов.
23. Какой алгоритм осуществляет построение оптимального дерева бинарного поиска:
а) Краскала;
б) Флери;
в) Робертса-Флореса;
г) Гильберта-Мура.
-
Глубина элемента а2 в дереве
равна
а) 0;
б) 1;
в) 2;
г) 3.
-
Степень вершины а2 в графе
равна
а) 0;
б) 1;
в) 2;
г) 3.
-
В оптимальном дереве бинарного поиска поиск завершается успешно в случае, когда:
а) корень отсутствует;
б) искомый элемент равен корню.
-
В оптимальном дереве бинарного поиска успешный поиск завершается
а) в листьях дерева;
б) во внутренних вершинах.
-
Алгоритм построения ОДБП организован:
а) снизу вверх;
б) сверху вниз.
-
Алгоритм построения ОДБП демонстрирует эффективность
а) метода ветвей и границ;
б) метода перебора Робертса-Флореса;
в) метода динамического программирования;
г) алгебраического метода поиска гамильтонового цила.
-
Стоимость дерева определяется формулой
а)
б)
в)
31. Алгоритм Краскала осуществялет:
а) построение дерева кратчайших путей;
б) построение оптимального дерева бинарного поиска;
в) построение кратчайшего остова.
32. В графе из n вершин остов содержит:
а) n+1 ребро;
б) n-1 ребро;
в) n ребер;
г) 2n ребер.
33. Дерево есть:
а) связный граф;
б) граф без циклов;
в) остовный подграф графа;
г) связный граф без циклов.
34. Простая цепь это:
а) маршрут минимальной стоимости;
б) маршрут, где нет повторяющихся вершин;
в) маршрут, где нет повторяющихся ребер;
г) маршрут, где нет повторяющихся вершин и ребер.
35. Расстояние между вершинами есть
а) сумма длин ребер, входящих в путь;
б) длина кратчайшего пути.
36. Алгоритм Дейкстры определяет:
а) кратчайший остов графа;
б) построение дерева кратчайших путей;
в) построение оптимального дерева бинарного поиска;
г) эйлеровы циклы графа.
37. В алгоритме Дейкстры текущие числовые метки
а) неубывают;
б) невозрастают;
в) равны нулю;
г) отрицательные.
38. В алгоритме Дейкстры текущая числовая метка определяется
а) сложением двух предыдущих;
б) вычитанием двух предыдущих;
в) по минимуму из двух предыдущих;
г) сложением с постоянной меткой и сравнением с предыдущей.
39. Постоянные метки в алгоритме Дейкстры
а) убывают;
б) возрастают;
в) неубывают.
40. Постоянно помеченные вершины
а) повторяются;
б) не повторяются.
41. Определение постоянно помеченной вершины включает:
а) вычисление текущих меток для всех вершин и нахождение минимума среди них;
б) вычисление текущих меток для всех вершин и нахождение максимума среди них;
в) вычисление текущих меток для всех вершин и нахождение их среднего арифметического.
42. Мощность замкнутого теоретико-множественного алфавита, порожденного шестиэлементным универсумом равна:
а) 36;
б) 64;
в) 32.
43. Можно ли модель цифрового объекта представить ориентированным графом?
а) да
б) нет
44. Комбинационная схема является конечным автоматом:
а) да
б) нет
47. Можно ли без логического элемента НЕ построить модель триггера?
а) да
б) нет
48. Является ли элемент 3И-НЕ, имеющий обратную связь, элементом памяти?
а) да
б) нет
49. Структуры “булев граф” и “булево дерево”:
а) являются идентичными
б) обе имеют сходящиеся разветвления
в) отличаются наличием сходящихся разветвлений
50. Структура “булев граф”
а) имеет сходящиеся разветвления
б) не имеет сходящихся разветвлений
51. Структура “булево дерево”
а) имеет сходящиеся разветвления
б) не имеет сходящихся разветвлений
52. СДНФ соответствует схеме типа “булево дерево”:
а) да
б) нет
55. Состояние конечного автомата не может измениться без наличия изменения на входах
а) да
б) нет
56.
Множество {0, 1, X,
}
является самым минимальным
теоретико-множественным замкнутым
алфавитом.
а) да
б) нет
57. Поведение триггера описывается булевыми функциями
а) да
б) нет
58. Значения функции 2ИЛИ равны соответственно 0-Х-1 при подаче последовательности наборов 0Х-ХХ-Х1:
а) да
б) нет
59. Число кубов в КП всегда меньше количества строк таблицы истинности
а) да
б) нет
60. Минимальное число кубов в КП ПЭ 16ИЛИ-НЕ равно 16
а) да
б) нет
61. Можно ли по КП ПЭ записать ДНФ?
а) да
б) нет
62. Существуют ли кубы, для которых результаты выполнения операций минимизации (оператор сограней) и поглощения равны?
а) да
б) нет
63. Переменная, определенная символом X в кубе покрытия, является в ПЭ
а) несущественной
б) существенной
64. Может ли КП неконстантной булевой функции иметь один куб?
а) да
б) нет
65.
КП не может иметь координаты, определенные
символом
.
а) да
б) нет
66. Реакция выходов комбинационной схемы на двоичный вектор не может иметь символов X
а) да
б) нет
67. Сколько кубов содержит минимальная кубическая форма представления сильносвязного графа, имеющего четыре вершины:
а) 16;
б) 8;
в) 1?
68. Количество дуг в графе, определенное кубом LL, равно:
а) 8;
б) 12;
в) 9.
69. Можно ли символами двухтактного алфавита описать поведение элемента 2ИЛИ-НЕ?
а) да
б) нет
71. Может ли КП элемента быть равно таблице истинности?
а) да
б) нет
74. В тривиальном автомате функция выходов не зависит от состояния автомата
а) да
б) нет
76. Существует ли ПЭ (примитивный элемент), имеющий минимальное кубическое покрытие без символов X?
а) да
б) нет
77. Возможна ли минимизация векторов
01X01X10
11X01110
а) да
б) нет
78. Выполнима ли операция поглощения для векторов
SE010XFP
JE010XSH
а) да
б) нет
79. Может ли граф, имеющий две вершины, описываться кубом КФПГ, равным FF?
а) да
б) нет
80. Какое минимальное число символов необходимо для описания информационных процессов?
а) один
б) два
в) четыре
81. Сколько двоичных векторов содержит куб 01X10X10?
а) один
б) два
в) четыре
82. КП – это минимизированная таблица истинности, записанная в алфавите {0,1,X}
а) да
б) нет
83. Всегда ли можно по КП ПЭ восстановить его таблицу истинности?
а) да
б) нет
84. Можно ли однозначно по КФПГ восстановить исходный граф?
а) да
б) нет
85. Два различных графа не могут иметь одинаковые КФПГ
а) да
б) нет
86. Можно ли с помощью КФПГ описать несвязные вершины?
а) да
б) нет
87. Может ли граф, имеющий две вершины, описываться кубом FL?
а) да
б) нет
88. Граф несвязных вершин нельзя описывать с помощью КФПГ
а) да
б) нет
89. Неориентированный граф можно описывать с помощью КФПГ
а) да
б) нет
90. Любой сильносвязный граф может быть представлен одним кубом
а) да
б) нет