e) построения СДНФ;
F) получения СКНФ.
Ответ: b,d,e,f
37. Какая из формул разложения Шеннона приводит к получению СКНФ:
a) 
;
b) 
c) 
d) 
9. Какие из приведенных уравнений истинны:
а) 
б) 
в) 
г) 
д) 
38. Кубическое покрытие (КП) логического элемента есть:
а) таблица переходов;
b) таблица истинности;
c) неполная таблица истинности;
d) минимизированная таблица истинности.
39. Какие из следующих утверждений истинны:
а) кубическое покрытие не может быть таблицей истинности;
b) куб обозначает плоскость, если он имеет два символа Х;
c) КП дискретного элемента не может иметь на выходных координатах символы Х;
d) число кубов в покрытии может быть больше числа строк таблицы истинности.
40. Какие из схем реализуют функцию 
1) все
2) ни одна
3) а
4) b
5) c
6) d
41. Какая из функций соответствует минимальной ДНФ для заданной карты Карно:
a) 
б) 
в) 
г) 
д) все
е) ни одна
Теория графов
1. Ребра называются смежными, если они
а) инцидентны одной и той же вершине
б) параллельны
в) являются кратными
2. Если две вершины соединены одной дугой, они называются
а) инцидентными
б) коинцидентными
в) смежными
3. Какие из графов являются подграфами данного графа G
а) 
б) 
в) 
г) 
4. Если любые две вершины графа можно соединить простой цепью, то граф называется:
а) связным;
б) несвязным;
в) деревом;
г) остовом.
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. Какой алгоритм осуществляет построение оптимального дерева бинарного поиска:
а) Краскала;
б) Флери;
в) Робертса-Флореса;
г) Гильберта-Мура.
24. Глубина элемента а2 в дереве 
равна
а) 0;
б) 1;
в) 2;
г) 3.
25. Степень вершины а2 в графе 
равна
а) 0;
б) 1;
в) 2;
г) 3.
26. В оптимальном дереве бинарного поиска поиск завершается успешно в случае, когда:
а) корень отсутствует;
б) искомый элемент равен корню.
27. В оптимальном дереве бинарного поиска успешный поиск завершается
а) в листьях дерева;
б) во внутренних вершинах.
28. Алгоритм построения ОДБП организован:
а) снизу вверх;
б) сверху вниз.
29. Алгоритм построения ОДБП демонстрирует эффективность
а) метода ветвей и границ;
б) метода перебора Робертса-Флореса;
в) метода динамического программирования;
г) алгебраического метода поиска гамильтонового цила.
30. Стоимость дерева определяется формулой
а) 
б) 
в) 
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. Структуры “булев граф” и “булево дерево”:
а) являются идентичными
б) обе имеют сходящиеся разветвления