Otvety_k_testam_po_DM


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.

1

Раздел 
.
«Теория множеств»


1.

Дано множество
. Какие из утверждений верны:

а)
;

б)
;

в)

;

г)
.

2.

Определить мощность множества
:

а)
;

б)

;

в)
;

г)
.

3.

Выбрать верный вариант формулы для определения мощности булеана
В(А):

а)
;

б)

;

в)
;

г)
.

4.

Определить мощность булеана множества
А{{
a
,
b
},
c
}:

а)
;

б)
;

в)
;

г)

.

5.

Выбрать верный порядок убывания старшинства операций алгебры
Кантора:

а)
;

б)
;

в)

;

г)
.

6.

Какая формула соответствует дистрибутивному закону:

а)
;

б)

;

в)
;

г)
.

7.

Указать формулу, соответствующу
ю закону Порецкого:

а)
;

б)
;

в)

;

г)
.


2

8.

Могут ли повторяться элементы множества?

а) да;

б)

нет
.

9.

Является ли множество несобственным подмножеством самого себя?

а)

да;

б) нет.

10.

Множества равны, если они содержат:


а)

одни и те же элементы;


б) одинаковое количество элементов.

11.

Являются ли понятия мощности множества и его кардинального числа
идентичными?

а)

да;

б) нет.

1
2
.
Булеан множества
А
{{, 2}, 3} определяется как
:

а)
;

б)
;

в)
;

г)

.

1
3
. Какое из утверждений верно для всех множеств А, В, С:

а) если

и
, то
;

б)

если

и
, то
;

в) если

и
, то
;

г) ни одно не верно.

1
4
.
Какой закон
определяется формулой
?

а)

элиминации;

б) Порецкого;

в) Де Моргана;

г)
инволюции.

1
5
.
Чему равно выражение
:

а)
;

б)
;

в)
;

г)

.

1
6
. Могут ли повторяться компоненты вектора?

а)

да;

б) нет.

1
7
. Длина вектора определяется:

а) чис
лом различных элементов;

б)

числом координат.

1
8
. Верно ли:
?

а) да;

б)

нет.



3

19
. Какое из соответствий называется взаимно
-
однозначным:

а) сюръективное, инъективное и функциональное?

б) сюръективное и инъективное?

в)

всюду определенно
е, сюръективное, инъективное и функциональное?

2
0
. Является ли отображение биективным, если оно сюръективно и
инъективно?

а)

да;

б) нет.

2
1
. Отображение А в В это:

а) частично определенная функция;

б)

всюду определенная функция;

в) сюръективное соответств
ие;

г) инъективное соответствие.

2
2
.
Указать определение инъективного соответствия

а)

;

б)
;

в)
;

г)
.

2
3
.
Какая из формул не задает функцию:

а)
;

б)
;

в)

;

г)
.

2
4
. Проекция соответствия

на первую ось равна


а)

б)


в)

г)

2
5
. П
роекция соответствия

на вторую ось равна


а)

б)

в)

г)


2
6
. Указать

проекци
ю

множества {(3,3,5), (3,3,6), (3,5,5), (3,5,6), (,3
,5),
(8,3,6), (8,5,5),
(,5,6)} на третью ось

а)
Pr
A={3,8},

б)
Pr
A={3,5},

в)

Pr
A={5,6}.

2
7
.
Верно ли: |А
n
| = |A|
n

?


а)

да

б) нет.


4

2
8
. Отношением степени n называется:


а) произвольное подмножество данного множества;


б) подмножество декартова произведения двух множеств;


в) п
одмножество декартова произведения любого конечного



количества множеств;


г)

подмножество декартовой степени множества
;


д) результат объединения данных множеств;


е) результат пересечения данных множеств.

29
. В каком случае

и

являются совместимыми?

а)
;

б)
;

в)

.

3
0
. Для каких из операций над отношениями выполнение условия
совместимости является не обязательным:

а)
;

б)
;

в)
\

;

г)

.

3
1
. Отношения являются совместимыми:


а) всегда;


б) если они имеют разные степени;


в)

если они имеют одинаковые степени;


г) если они бинарные.

3
2
. Какие из операций реляционной алгебры применимы к отношени
ям
:

а)
;

б)
;

в)
\

;

г)

.

д) все;

е) ни одна не применима.

3
3
. Какие из операций реляционной алгебры применимы к отношениям
:

а)
;

б)
;

в)
\

;

г)
;

д) все;

е) ни одна не применима.





5

3
4
. Операция выбора представляет собой построение:

а)

«горизонтального» подмножества отношения;

б)

«вертикального» подмножества отношения
;

в) «диагонального»
подмножества отношения;

г) «бинарного» подмножества отношения;

3
5
. Операция проекции представляет собой построение:

а)

«горизонтального» подмножества отношения
;

б)

«вертикального» подмножества отношения;

в) «диагонального» подмножества отношения.

3
6
. Опе
рация проекции по двум доменам представляет собой построение:

а)

«горизонтального» подмножества отношения
;

б)

«вертикального» подмножества отношения
;

в) «диагонального» подмножества отношения;

г)

бинарного подмножества отношения.

3
7
. Операция проекции по

одному домену представляет собой построение:

а)

«горизонтального» подмножества отношения
;

б)

«вертикального» подмножества отношения
;

в) «диагонального» подмножества отношения;

г) бинарного подмножества отношения;

д) некоторого отношения степени n;

е)

мн
ожества элементов, не являющегося отношением.

3
8
. Какое из отношений является бинарным:

а)
;


б)

;




в)
.

39
. Если матрица, описывающая бинарное отношение, содержит на главной
диагонали и нули и

единицы, то отношение:

а) рефлексивно;

б) антирефлексивно;

в)

не рефлексивно.

40
. Если все вершины графа, описывающего отношение, имеют петли, то
отношение:

а)

рефлексивно;

б) антирефлексивно;

в) не рефлексивно.

41
. Если в графе, описывающем отношен
ие, имеется хотя бы одна пара
вершин, соединенных одной дугой, является ли данное отношение
симметричным?

а) да;

б)

нет.

42
. Классы эквивалентности:

а) попарно пересекаются;

б)

попарно не пересекаются.


6

43
. Верно ли, что любые два элемента из одного класс
а эквивалентности
эквивалентны?

а)

да;

б) нет.

44
. Верно ли, что любые два элемента из разных классов эквивалентности не
эквивалентны?

а) да;

б)

нет.

45
. Если отношение антирефлексивно, антисимметрично и транзитивно, оно
является:

а) отношением нестрогог
о порядка;

б)

отношением строгого порядка;

в) не является отношением порядка.

46
. Если любые два элемента множества M, на котором задано отношение
порядка, сравнимы, М является:

а) неупорядоченным;


б)

линейно упорядоченным;


в) частично упорядоченным;

47
.

Среди следующих отношений, заданных на множестве отрезков, укажите
отношение порядка:

а) отрезок х равен отрезку у;

б) отрезок х короче отрезка у в 2 раза;

в)

отрезок х длиннее отрезка у.

48.
Дано множество
. Какие из утверждений верны
:

а
)
;

б)

;

в)

;

г)

.

49.

Определить мощность множества
:

а)
;

б)

;

в)

;

г)
.

50.

Оп
ределить мощность булеана множества
:

а)
;

б)
;

в)
;

г)

.

51.
Указать формулу, соответствующую закону элиминации:

а)
;

б)
;

в)

;


7

г)

.

52
.

Указать несобственные подмножествами множества
:

а)

;

б)
;

в)

;

г)
;

д)
.

53. Множества имеют одинаковую мощность, если они содержат:

а)

одни и те же элементы;

б)

одинаковое количество элементов.

54. Кардинальное число определяет:

а)

количество элементов булеана данного множества;

б)

количество элементов данного множества.

5
5.
Булеан множества
определяется как
:

а)
;

б)
;

в)

;

г)
.

56. Какой закон
определяется формулой
?

а)

элиминации;

б)

Порецкого;

в) Де Мор
гана;

г) инволюции

57.
Чему равно выражение
:

а)
;

б)
;

в)
;

г)

;

д)
;

е)
.

5. Чему равна мощность булеана множеств
а
:

а)
;

б)
;

в)
;

г)

.

59. Операция объединения двух множеств есть совокупность

элементов:

а) различных для этих множеств;

б)

принадлежащих одному или друг
ому множеству;

в) принадлежащих обоим множествам.

60. Операция пересечения двух множеств есть совокупность:

а)

элементов, одинаковых для этих множеств;


8

б) элементов, различных для этих множеств;

в) элементов, принадлежащих одному или другому множеству.

61.

Операция симметрической разности обозначается символом:

а)
;

б)

;

в)

;

г)

.

62. Размерность вектора есть:

а)

количество всех его компонентов;

б)

количество различных его комп
онентов.

63. Какое из данных соответствий является всюду определенным:

а)




б)





в)











64. Какое из данных соответствий является функциональным:

а)





б)





в)










65. Какое из данных соответствий является инъективным:

а)





б)




в)











66. Какое из данных соответствий является биективным:

а)




б)




в)




г)







67. Какие соответствия не являются инъективными:

а)




б)





в)




г)





6. Какие соответствия не являются функци
ональными:

а)





б)




в)




г)


9

69. Какие соответствия являются сюръективными:

а)





б)




в)




г)







70. Какие соответствия являются всюду определенными:

а)




б)





в)




г)







7. Какой из законов не обязатель
но присутствует в определении решетки:

а) коммутативный;

б)

дистрибутивный;

в) элиминации;

г) ассоциативный?

72. Какой закон в дополнение к обязательным определяет решетку как
булеву алгебру:

а)

дистрибутивный;

б) коммутативный;

в) элиминации;

г) ас
социативный?

73. Решетка определяется на:

а)

произвольном множестве;

б) линейно упорядоченном множестве;

в)

частично упорядоченном множестве;

г) неупорядоченном множестве?

74. Какое из условий определяет дедекиндову решетку:

а)
;

б)

;

в)
;

г)
,

д)
,

е)


75. Какое из условий определяет дистрибутивную решетку в дополнение к
свойству модулярности:

а)
;

б)
;

в)
;

г)
,


10

д)
,

е)


Раздел 2
. Комбинаторный анализ


. Число перестановок из 5 элементов равно:

а) 5; б) 25;
в)

120
; г)
1.

2. Имеет ли подстановка


неподвижную точку

а)

да;

б) нет.

3. Имеет ли подстановка

инверсии

а)

да;

б) нет.

4. Являются ли перестановки с повторениями различными: А Б С, А Б А?

а)

да;

б) нет.

5. Являются ли перест
ановки различными:

А А Б, А Б А;


А В С, А В А;

а)

да;

б) нет.

6. Сколькими способами можно расставить на полке 4 книги?

а) 4

б)

4!

в)

г)
.

7. Являются ли перестановки с повторениями различными: А А Б, А Б А?

а)

да
;

б) нет.

8
. Выбрать верный вариант:

а)

при
k

n

б)


при
k

n

9
. Биномиальные коэффициенты определяются формулой:

а)


11


б)


в)


г)


10
.

Полиномиальные коэффициенты определяются формулой:

а)


б)


в)


г)

11
. Выбрать верный вариант:

а)

б)


в)

12
. В
ыбрать верный вариант:

а)

б)

в)


13
. Выбрать верный вариант:

а)

б)


в)

14
. Свойство симметрии биномиальных коэффициентов определяетс
я как:


а)


б)


в)



12

1
5
. Сколько существует способов выбрать 3 книги из 5?

а) 0;

б) ;

в)
;

г)

.

16
. Являются ли сочетания с повторениями различными: МА
МА, МАША?

а)

да
;

б) нет.

17
. Являются ли сочетания с повторениями различными: ПАПА, АППА?

а) да;

б)

нет
.

18
. Какие из сочетаний с повторениями являются различными?

а)

МАМА, МАША
;

б) ПАПА, АППА;

в) ПАРА, РАПА.

19
. Какие из размещений являются идентичными:

а)

abcba, abcba
;

б)
abc
,
cba
;

в) bce, bc.

20
. Какие из сочетаний являются идентичными:

а) 23, 232;

б)

abc
,
cba
;

в)

КСМ, МСК.

21
. Сколькими способами можно рассадить 4 человека на n местах?

а) 4

б) 4!

в)

г)


д)

22
. Указать формулу для определения числа размещений:

а)

б)


13

в)


23
.
Какие комбинаторные конфигурации

явля
ю
тся
упорядоченными
:


а) перестановки;


б) размещения;


в)

сочетания.

24
. В каком случае мощность множества больше:


а) в размещении без повторений;


б)

в размещении с повторениями;


в) одинаково.

25
. Является ли размещение перестановкой:


а) никогда;


б) всегда;


в)

да, при k;

г)

да, при
k
=
n
.



Раздел 3
. Булева алгебра


1
.

Сколько двоичных наборов содержит таблица истинности функции
f(a,b,c)?

а) 2;

б) 3;

в) 7;

г)

8?

2.

Какая из формул допускает упрощение:

а)
;

б)

;

в)
;

г)
?

3.

Какая из ф
ормул представляет закон элиминации:

а)
;

б)

;

в)
;

г)
?

4.

Чему равно логическое выражение
:

а) 0;

б)
;

в)

;

г) ?


14

5.

Предельное дизъюнктивное разложение функции по теореме Шеннона
есть

а) СКНФ;

б)

СДНФ;

в) ДНФ;

г) КНФ?

6.

На каком входном наборе конъюнкция двух переменных равна единице:

а) 0,0;

б) 0,;

в) ,0;

г)

1,1.

7. На каком входном наборе дизъюнкция

двух переменных равна единице:

а)

0,0;

б) 0,;

в) ,0;

г) ,.

. Конъюнкция некоторого числа переменных равна единице, когда:


а)

все переменные равны единице;


б) все переменные равны нулю;


в) хотя бы одна переменная равна единице;


г) хотя бы одна
переменная равна нулю.

9. Дизъюнкция некоторого числа переменных равна единице, когда:


а) все переменные равны единице;


б) все переменные равны нулю;


в)

хотя бы одна переменная равна единице;


г) хотя бы одна переменная равна нулю.

1
0
.

Чему равно выраж
ение
:

а)
;

б)
;

в)
;

г)

?

11
. Какой элемент реализует функцию логического сложения:


а)


б)


в)


г)

12
. Какой элемент реализует функцию логическ
ого умножения:


а)


15


б
)


в)


г)

13
. Какой функциональный элемент соответствует сумме по модулю 2:


а)


б)


в)


г)

14
. Какой элемент соответствует функции равнозначности:


а)


б)


в)


г)

1
5
. Функция

является самод
войственной?

а)

да;


б)

нет.

16
.

Функция

является:

а) сохраняющей единицу;

б)

сохраняющей ноль;

в) монотонной?

17
.

Функция

является:

а) самодвойственной;

б)

сохраняющей единицу;

в) сохраняющей ноль;

г) моното
нной?

1
8
.

Какие из кубов представляют точку:

а)

0
-
куб;

б) 
-
куб;

в) 2
-
куб;

г) любой.

19
.

Какие из кубов задают отрезок:

а) 0
-
куб;

б)

1
-
куб;

в) 2
-
куб;

г) любой.

20
.

Какие из кубов представляют плоскость:

а) 0
-
куб;

б) 
-
куб;

в)

2
-
куб;

г) любой.


16

21
.

Указать к
уб, который геометрически можно интерпретировать как
плоскость:

а) Х00;

б)

0ХХ;

в) 0;

г) любой.

22
.

Указать куб, который геометрически можно интерпретировать как
отрезок:

а) Х0Х;

б)

0Х;

в) 0;

г) любой.

23
.

Указать куб, который геометрически можно инте
рпретировать как точку:

а) 00;

б) 0ХХ;

в)

0Х;

г) любой.

24
.

Куб Х геометрически можно интерпретировать как:

а) плоскость;

б)

отрезок;

в) точку.

25
.

Указать, какие кубы склеиваются:

а)

Х00, Х0 ;

б) 0, 00;

в) 0Х, 0Х;

г) ни одна пара не склеивается
.

26
.

Склеивание кубов 00 и 0 дает:

а) Х00;

б) 0ХХ;

в) 0;

г)

0Х.

27
.

Куб ХХ является

а) 
-
кубом;

б)

2
-
кубом;

в) 0
-
кубом.

28
.

Куб 00Х является

а)

1
-
кубом;

б) 2
-
кубом;

в) 0
-
кубом.

29
.

Куб 0 является

а) 
-
кубом;

б) 2
-
кубом;

в)

0
-
кубом.

30
.

Каждая имп
ликанта в СДНФ соответствует

а) нулевому значению функции;


17

б)

значению функции, равному единице.

31
.

Каждая импликанта в СКНФ соответствует

а)

нулевому значению функции;

б) значению функции, равному единице.

3
2
. Первая производная функции по
переменной
x

равна
. Какие
значения сигналов не являются условием возможной активизации выхода
при изменении сигнала x:

а) ,0;


б) 0,;




в) ,;




г)

0,0 ?

33
. Альтернативное понятие для минимизации есть:

) факторизация;

б
) поглощение;

в
) буле
визация;

г) разложение.

34
. Поставить в соответствие функциям их таблицы истинности:


1)

а

b

c

d

2)


а

b

c

d

3)

а

b

c

d

4)

а

b

c

d

3
5
. Поставить в соответствие кубическим покрытиям их таблицы
истинности:


1)

а

b

c

d

2)


а

b

c

d

3)

а

b

c

d

4)

а

b

c

d

3
6.
Разложение булевой функции по Шеннону предназначено для:

а) факторизации;

b) максимизации;


18

c) минимизации;

d) получения таблицы истинности

e) построения СДНФ;

f) получения СКНФ.

Ответ: b,d,e,f

3
7. Какая из формул разложения Шеннона приводит к получению СКН
Ф:

a
)
;

b
)

c
)

d
)

9. Какие из приведенных уравнений истинны:

а)

б)


в)

г)

д)

38
. Кубическое покрытие (КП) логического элемента есть:

а) таблица переходов;

b) таблица истинности;

c) неполная таблица истинности;

d) минимизированная таблица истинности.

39
. Какие из следующих утверждений истинн
ы
:

а) ку
бическое покрытие не может быть таблицей истинности;

b) куб обозначает плоскость, если он имеет два символа Х;

c) КП дискретного элемента не может иметь на выходных
координатах символы Х;

d) число кубов
в
покрытии может быть больше числа строк таблицы
исти
нности.

40
. Какие из схем реализуют функцию




19

1)
все

2)
ни одна

3)
а

4)
b

5)
c

6)
d

4. Какая из функций соответствует минимальной
ДНФ
для заданной карты
Карно:



a
)


б)

в)

г)

д
)
все

е
)
ни одна

Раздел 4
. Теория графов

. Ребра называются смежными, если они

а)

инцидентны одной и той же вершине

б) параллельны

в) являются кратными

2. Если две вершины соединены одной дуго
й, они называются

а) инцидентными

б) коинцидентными

в)

смежными

3. Какие из графов являются подграфами данного графа G



а)


б)
в)

г)


4.

Если любые две вершины графа можно соединить простой цепью, то
граф называется:


20

а)

связным;

б) несвязным;

в) дерев
ом;

г) остовом.

5
. Сколько вершин содержит гамильтонов цикл графа с 5 вершинами?

а)

5

б) 4

в) 6

6
. Граф содержит 7 дуг. Его эйлеров цикл будет состоять из

а) 6 дуг

б)

7 дуг

в)  дуг

7
.

Эйлеров цикл

а)

содержит каждое ребро только один раз;

б) содержит каж
дую вершину только один раз;

в) проходит через все вершины и ребра графа только один раз.

8
. Гамильтонов цикл

а) содержит каждое ребро только один раз;

б)

содержит каждую вершину только один раз;

в) проходит через все вершины и ребра графа только один раз
.

9
.

В эйлеровом графе все вершины

а)

четной степени;

б) нечетной степени.

10
.

В
полу
эйлеровом графе допускаются

а) 3 вершины нечетной степени;

б)

2 вершины нечетной степени;

в)  вершина нечетной степени.

11
.

Какой алгоритм определяет гамильтоновы циклы
графа:

а) Гильберта
-
Мура;

б) Флери;

в)

Робертса
-
Флореса;

г) Дейкстры.

12
.

Какой из циклов графа с множеством вершин {
a
,
b
,
c
,
d
,
e
,
f
} является
гамильтоновым?

а)
abeca

б)
fbecdf

в)

abecdfa

г)
abcdfca

13
.

Какой граф является гамильтоновым:

а)








21



б)






в)





14
.

В алгебраической форме представления графов аксиома о единичном
элементе формулируется следующим образом:

а)


б)

в)

г)


15
.

В алгебраической форме представления

графов имеет ли место свойство
коммутативности относительно операции конкатенации для
ориентированных графов?

а) да

б)

нет.

16
.

Правило минимизации фрагмента графа:

а)
;

б)
;

в)

.

17
.

Какая из ак
сиом абстрактной математической решетки не содержится в
АФПГ:

а) ассоциативность;

б) дистрибутивность;

в) аксиома о единичном элементе;

г)

аксиома о нулевом элементе.

18.

Задача коммивояжера решается при помощи:

а) алгоритма Гильберта
-
Мура;

б)

метода ветв
ей и границ;

в) алгоритма Краскала;

г)

метода динамического программирования.

19.
Увеличение нижней границы стоимостей решений в левых узлах
поддерева осуществляется за счет:

а) выбора в преобразованной матрице стоимостей нуля, который при замене
его на бе
сконечность позволяет вычесть наибольшее суммарное количество
из строки и столбца, на пересечении которых он находится;


22

б)

вычитания из строк и столбцов матрицы после понижения ее порядка
минимальных элементов.

20
. Выбор в преобразованной матрице стоимосте
й нуля, который при замене
его на бесконечность позволяет вычесть наибольшее суммарное количество
из строки и столбца, на пересечении которых он находится, определяет
увеличение нижней границы стоимостей решений

а) в левых узлах поддерева;

б)

в правых уз
лах поддерева.

21
. Вычитание из строк и столбцов матрицы после понижения ее порядка
минимальных элементов определяет увеличение нижней границы стоимостей
решений:

а)

в левых узлах поддерева;

б) в правых узлах поддерева.

22
. Увеличение нижней границы стоим
остей решений в
правых

узлах
поддерева осуществляется за счет:

а)

выбора в преобразованной матрице стоимостей нуля, который при
замене его на бесконечность позволяет вычесть наибольшее суммарное
количество из строки и столбца, на пересечении которых он нах
одится;

б) вычитания из строк и столбцов матрицы после понижения ее порядка
минимальных элементов.

23.
Какой алгоритм осуществляет построение оптимального дерева
бинарного поиска:

а) Краскала
;

б) Флери;

в) Робертса
-
Флореса;

г)

Гильберта
-
Мура.

24.

Глубина элеме
нта а
2
в дереве

равна

а) 0;

б)

1;

в) 2;

г) 3.

25.

Степень вершины а
2
в графе

равна

а) 0;

б) ;

в) 2;


23

г)

3.

26.

В оптимальном дереве бинарного поиска поиск завершается успешно в
случае, когда:

а) корень отсутствует;

б)

искомый элемент равен корню.

27.

В оптим
альном дереве бинарного поиска успешный поиск завершается

а) в листьях дерева;

б)

во внутренних вершинах.

28.

Алгоритм построения ОДБП организован:

а)

снизу вверх;

б) сверху вниз.

29.

Алгоритм построения ОДБП демонстрирует эффективность

а) метода ветвей и границ;

б) метода перебора Робертса
-
Флореса;

в)

метода динамического программирования;

г) алгебраического метода поиска гамильтонового цила.

30.

Стоимость дерева определяется формулой

а)


б)

в)

3
1.

Алгорит
м Краскала осуществялет:

а) построение дерева кратчайших путей;

б) построение оптимального дерева бинарного поиска;

в)

построение кратчайшего остова.

3
2.

В графе из
n

вершин остов содержит:

а)
n
+
1

ребро;

б)

n
-
 ребро;

в)
n

ребер;

г)
2
n

ребер.

3
3
.

Дерево ес
ть:

а) связный граф;

б) граф без циклов;

в) остовный подграф графа;

г)

связный граф без циклов.

3
4.

Простая цепь это:

а) маршрут минимальной стоимости;

б) маршрут, где нет повторяющихся вершин;

в) маршрут, где нет повторяющихся ребер;

г)

маршрут, где нет п
овторяющихся вершин и ребер.

3
5.

Расстояние между вершинами есть

а) сумма длин ребер, входящих в путь;


24

б)

длина кратчайшего пути.

3
6.

Алгоритм Дейкстры определяет:

а) кратчайший остов графа;

б)

построение дерева кратчайших путей;

в) построение оптимальног
о дерева бинарного поиска;

г) эйлеровы циклы графа.

3
7.

В алгоритме Дейкстры текущие числовые метки

а) неубывают;

б)

невозрастают;

в) равны нулю;

г) отрицательные.

3
8.

В алгоритме Дейкстры текущая числовая метка определяется

а) сложением двух предыдущих;

б) вычитанием двух предыдущих;

в) по минимуму из двух предыдущих;

г)

сложением с постоянной меткой и сравнением с предыдущей.

3
9.

Постоянные метки в алгоритме Дейкстры

а) убывают;

б) возрастают;

в)

неубывают.

4
0.

Постоянно помеченные вершины

а) повторяются
;

б)

не повторяются.

4
1.

Определение постоянно помеченной вершины включает:

а)

вычисление текущих меток для всех вершин и нахождение
минимума среди них;

б) вычисление текущих меток для всех вершин и нахождение максимума
среди них;

в) вычисление текущих мет
ок для всех вершин и нахождение их среднего
арифметического.


4
2
. Мощность замкнутого теоретико
-
множественного алфавита,
порожденного шестиэлементным универсумом равна:

а
) 36;

б) 64;

в
) 32.

4
3
. Можно ли модель цифрового объекта представить ориентирова
нным
графом?

а) да

б) нет

4
4
. Комбинационная схема является конечным автоматом
:

а) да


25

б) нет

47
. Можно ли без логического элемента НЕ построить модель триггера?

а) да

б) нет

48
. Является ли элемент 3И
-
НЕ, имеющий обратную связь, элементом
памяти?

а) да

б)
нет

49
. Структур
ы

“булев граф”
и

“булев
о

дерев
о

:

а) являются идентичными

б) обе имеют сходящиеся разветвления

в) отличаются наличием сходящихся разветвлений

50
. Структур
а

“булев граф”

а) имеет сходящиеся разветвления

б) не имеет сходящихся разветвлений

5
1
. Структур
а

“булев
о

дерево


а) имеет сходящиеся разветвления

б) не имеет сходящихся разветвлений

5
2
. СДНФ соответствует схеме типа “булево дерево”
:

а) да

б) нет

55. Состояние конечного автомата не может измениться
без наличия
изменения на входах

а) да

б)

нет

56. Множество {0,

1,

X,

} является самым минимальным теоретико
-
множественным замкнутым алфавитом.

а) да

б)

нет

57. Поведение триггера описывается булевыми функциями

а) да

б)

нет

5. Значения функции 2ИЛИ равны соответственно 0
-
Х
-
 при подаче
последова
тельности наборов 0Х
-
ХХ
-
Х:

а) да


26

б)

нет

59. Число кубов в КП всегда меньше коли
чества строк таблицы истинности

а) да

б) нет

60. Минимальное число кубов в КП ПЭ 6ИЛИ
-
НЕ равно 6

а) да

б) нет

6. Можно ли по КП ПЭ записать ДНФ?

а) да

б)

нет

62. Существуют ли кубы, для которых результаты выполнения операций
минимизации (оператор сограней) и поглощения равны?

а) да

б)

нет

63. Переменная, определенная символом X в кубе покрытия, является в ПЭ

а) несущественной

б)
существенной

64. Может л
и КП
неконстантной
булевой функции иметь один куб?

а)

да

б) нет

65. КП не может иметь координаты, определенные символом

.

а) да

б) нет

66. Реакция выходов комбинационной схемы на двоичный вектор не может
иметь символов X

а) да

б) нет

67. Сколько кубов содержит минимальная кубическая форма представления
сильносвязного графа, имеющего четыре вершины:

а) 6;

б
) 8;

в
) 1?

6. Количество дуг в графе, определенное кубом LL, равно:

а
) 8;

б
) 12;


27

в) 9.

69. Можно ли символами двухтактного
алфавита описать поведение элемента
2ИЛИ
-
НЕ?

а) да

б) нет

7. Может ли КП элемента быть равно таблице истинности?

а) да

б) нет

74. В тривиальном автомате функция выходов н
е зависит от состояния
автомата

а) да

б) нет

76. Существует ли ПЭ

(примитивный элемен
т)
, имеющий минимальное
кубическое покрытие без символов X?

а) да

б) нет

77. Возможна ли минимизация векторов

01X01X10

11X01110

а) да

б) нет

7. Выполнима ли операция поглощения для векторов

SE010XFP

JE010XSH

а) да

б) нет

79. Может ли граф, имеющий две вер
шины, описываться кубом КФПГ,
равным FF?

а) да

б) нет

0. Какое минимальное число символов необходимо для описания
информационных процессов?

а) один

б) два

в) четыре


28

. Сколько двоичных векторов содержит куб 0X0X0?

а) один

б) два

в) четыре

2. КП


это

минимизированная таблица истинности, записанная в алфавите
{0,1,X}

а) да

б) нет

3. Всегда ли можно по КП ПЭ восстановить его таблицу истинности?

а) да

б) нет

4. Можно ли однозначно по КФПГ восстановить исходный граф?

а) да

б) нет

5. Два различных графа

не могут иметь одинак
овые КФПГ

а) да

б) нет

6. Можно ли с помощью КФПГ описать несвязные вершины?

а) да

б) нет


7. Может ли граф, имеющий две вершины, описываться кубом FL?

а) да

б) нет

. Граф несвязных вершин нельзя описывать с помощью КФПГ

а) да

б)
нет

9. Неориентированный граф можно описывать с помощью КФПГ

а) да

б) нет

90. Любой сильносвязный граф может быть представлен одним кубом

а) да

б) нет


Приложенные файлы

  • pdf 17493543
    Размер файла: 818 kB Загрузок: 2

Добавить комментарий