Тесты для самоконтроля

ЗАДАНИЯ

ВАРИАНТЫ ОТВЕТОВ

1. Установите соответствие между высказываниями

1. Объединением множеств А и В называется множество АВ, все элементы которого являются….

2. Пересечением множеств А и В называется множество АВ, все элементы которого являются ….

3. Относительным дополнением множества В до множества А называется множество А \ В, все элементы которого являются …

4. Симметрической разностью множеств А и В называется …

А) элементами обоих множеств А и В.

В) элементами множества А, но не являются элементами множества В

С) элементами хотя бы одного из множеств А или В.

D)множество всех таких элементов x  U, которые не принадлежат множеству А: = U \ A.

Е) множество А + В:

А + В = (А \ В)  (В \ А).

2. Установите соответствие между левой и правой частями тождеств алгебры множеств

1. A  B =

2. =

3. A  (A  B) =

4. =

А) A

В) 

С) B  A

D) 

Е) B  A

3. Установите соответствие между списками двух множеств, заданных различным образом:

1.

2.

3.

4.

А){2:3}

В)(2;3)

С)(-∞; 2) (3; +∞)

D)(-∞; 2] [3; +∞)

Е) [2; 3]

4. Пусть U= {1,2,3,4}, А={1,3,4}, В={2,3}, С={1,4}. Тогда

1.  =

2. =

3. (В\А)  =

А) {1,2,4},

В) {1,4},

С) {2,3},

5.Сколько имеется пятизначных чисел, которые делятся еа 5?

1) 12000; 2) 15000;

3) 18000; 4) 9000

6. На рояле 88 клавиш. Сколько существует последовательностей из шести попарно различных звуков? (В последовательности звуки идут один за другим) Сколько существует аккордов из шести звуков? (Аккорд получается, если любые 6 клавиш нажаты одновременно).

1) аккордов и

последовательностей;

2) аккордов и

последовательностей;

3) последовательностей и

аккордов.

7. При обследовании читательских вкусов оказалось, что 60% студентов читают журнал А, 50% - журнал В, 50% - журнал С, 30% - журналы А и В, 20% - журналы В и С, 40% - журналы А и С, 10% - журналы А, В и С. Сколько процентов студентов не читает ни одного журнала?

1) 10%; 2) 20%; 3) 15%; 4) 25%

8. Число положительных чисел, не превосходящих 100 и не делящихся ни на одно из чисел 3, 5 и 7 равно…

1) 258; 2) 457; 3) 287; 4) 241.

9. Установите соответствие между высказываниями

1.Областью определения бинарного отношения  называется …

2. Областью значений бинарного отношения  называется…

3. Областью задания бинарного отношения  называется…

А) множество

R_ = {y существует x, что x y}.

В) множество M_ = D_  R_.

С) множество

D_ = {x существует y, что x y}.

10. Установите соответствие между высказываниями

1. Отношение  называется рефлексивным на множестве X, если …..

2. Отношение  называется симметричным на множестве X, если …

3.Отношение  называется транзитивным на множестве X, если …

4.Отношение  называется антисимметричным на множестве X, если…

А) для любых x, y  X из xy следует y x.

В) для любого x X выполняется x x.

С) для любых x, y  X из xy и y x следует x = y.

D) для любых x, y, z  X из xy и y z следует x z.

11. Пусть отношение R – «быть руководителем», определенное на множестве сотрудников организации М. Каковы свойства этого отношения?

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

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

3) симметрично;

4) транзитивно.

12. Дана реализация графа. Соответствующим ей множеством вершин (V) и списком дуг (Е) является

1) V= {1,2,3,4};

Е={(1,3),(3,1), (3,2),(4,4), (4,3)};

2) V= {1,2,3,4};

Е={(1,3),(3,1), (3,2),(4,4), (3,4)};

3) V= {1,2,3,4};

Е={(2,3),(1,3), (3,1),(4,4), (3,4)};

4) V= {1,2,3,4};

Е={(1,3),(3,4), (2,32),(3,1)}.

14. Матрица смежности изображенного графа имеет вид

1) ; 2) ;

3) ; 4)

15. Матрица смежности изображенного графа имеет вид

1) ; 2) ;

3) ; 4)

16. Среди приведенных графов указать те, которые имеют собственный Эйлеров цикл.

1)

2)

3)

1 7. Сумма степеней вершин первого и второго типа изображенного графа равна…

1) 6; 2) 7; 3) 4; 4) 5.

18. Компонентой связности неориентированного графа называется ….

1) его односторонне связный подграф, не являющийся собственным подграфом никакого другого односторонне связного подграфа данного графа

2) его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа данного графа

3) его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа.

19. Какая модель теории графов адекватна следующей задаче: Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.

1) нахождение минимального пути;

2) нахождение максимального пути

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

4)нахождение экстремального пути.

20. Какая модель теории графов адекватна следующей задаче:

Имеется схема городских дорог с перекрестками и, возможно, однос­торонним движением. Необходимо найти маршрут, соединяющий две точки на карте. Как найти такой маршрут при условии, что его длина минимальна?

1) нахождение минимального пути;

2) нахождение максимального пути

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

4)нахождение экстремального пути.

21. Установите последовательность действий алгоритма Форда Беллмана:

Шаг 1

Шаг 2.

Шаг 3

Шаг 4.

А) Восстановление минимального пути. Для любой вершины x_s предшествующая ей вершина x_r определяется из соотношения:

_r(n – 2) + c_rs = _s(n – 1), x_rÎ G^-1(x_s),

где G^-1(x_s) - прообраз вершины x_s.

В)Установка начальных условий. Ввести число вершин графа n и матрицу весов C = (c_ij).

С) Положить k = 0. Положить _i(0) = ¥ для всех вершин, кроме х₁; положить ₁(0) = 0.

D) В цикле по k, k = 1,..., n – 1, каждой вершине x_i на k-ом шаге приписать индекс _i(k) по следу­ющему правилу:

_i(k) = {_j(k – 1) + c_ji} для всех вершин, кроме х₁, положить ₁(k) = 0.

22. Всего существует ……. Различных булевых функций для п переменных.

1) ; 2) ; 3) ; 4)

23. Какое из следующих утверждений верно?

1) Переменные булевой функции и сама булева функция принимают значения 0 или 1;

2) Переменные булевой функции принимают значения 0 или 1, а значения самой булевой функции совпадают с множеством действительных чисел;

3) Значения переменных булевой функции совпадают с множеством действительных чисел, а сама булева функция принимает значения 0 или 1;

4) Значения переменных булевой функции и значения самой функции совпадают с множеством действительных чисел;

24. Укажите номера выражений, являющихся формулами

1) (xVy)&((y  z) ~ x)

2)x&y  z  ~x

3) x&(yz)

26. Установите соответствие

1. Дистрибутивность.

2. Закон де Моргана.

3. Идемпотентность.

4. Поглощение.

5. Расщепление (склеивание).

А)

а) A&(AVB)  A ;

б) AVA&B  A .

В)

а) A&A  A (для конъюнкции);

б) AVA  A (для дизъюнкции).

С)

а) (A&B)AVB (отрицание конъюнкции есть дизъюнкция отрицаний);

б) (AVB) A&B (отрицание дизъюнкции есть конъюнкция отрицаний).

D)

а) A&(BVC)  A&BVA&C (для конъюнкции относительно дизъюнкции);

б) AV(B&C)  (AVB)&(AVC) (для дизъюнкции относительно конъюнкции).

Е)

а)A&B V A&(B)  A);

б) (AVB) & (AVB)  A .

27. Дизъюнктивная нормальная форма для функции

f(x₁, x₂, x₃) = (x₂ x₃) ~ (x₁Vx₂)

имеет вид

1) f(x₁, x₂, x₃)  x₂&x₃ V x₁&x₂

2) f(x₁, x₂, x₃)  x₂⌐x₃ V x₁&x₂

3) f(x₁, x₂, x₃)  x₂&x₃ ⌐x₁&x₂

28. Совершенная конъюнктивная нормальная форма для функции

f(x₁, x₂, x₃) = (x₂ x₃) ~ (x₁Vx₂)

имеет вид

1) f(x₁, x₂, x₃)  ≡(x₁Vx₂Vx₃)V(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃),

2) f(x₁, x₂, x₃)  ≡(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃),

3) f(x₁, x₂, x₃)  ≡⌐(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃)&(x₁Vx₂Vx₃).

29. Выберите правильный вариант ответа 1 – 4 для следующих вопросов:

А) Сколько может быть различных ДНФ у булевой функции?

В) Сколько может быть различных СДНФ у булевой функции?

С) Сколько может быть различных КНФ у булевой функции?

D) Сколько может быть различных СКНФ у булевой функции?

Варианты ответа:

1 – ноль или одна;

2 – ноль или бесконечно много;

3 – бесконечно много;

4 – одна;

5 – одна или бесконечно много.

30. В какой из нормальных форм находится данная формула булевой функции трех переменных f(x, y, z):

1.ДНФ

2. СДНФ

3. КНФ

4. СКНФ

А) xVy&z;

В) x&y&z;

С)(xVy)&(xVz);

D) xVyVz .