《离散数学》考试试卷(试卷库14卷)及答案
别妄想泡我
525次浏览
2021年01月29日 00:52
最佳经验
本文由作者推荐
运动会致辞-挥手告别打一字
《离散数学》考试试卷（试卷库
14
卷）
试题总分：
100
分
考试时限：
120
分钟
题号
得分
一
二
三
四
五
总分
阅卷人
一、选择题（
每题
2
分，共
20
分
）
1.
下述命题公式中，是重言式的为
( )
（
A
）
(
p
q
)
(
p
q
)
（
B
）
p
q
((
p
q
)
(
q
p
))
（
C
）
(
p
< br>q
)
q
（
D
）< br>(
p
q
)
q
2.
对任意集合
A,B,C,
下列结论正确的是（
）
（
A
）若
A
B,B
C,
则
A
C
；
（
B
）若
A
B,B
C,
则
A
C；
（
C
）若
A
B,B
C,
则
A
C
；
（
D
）若A
B,B
C,
则
A
C
；
3.
设
S
{
1
,
2
,
3
}
，定义
S
S
上的等价关系
,
S
S上一个划分共有
( )
个分块。
（
A
）
4
（
B
）
5
（
C
）
6
（
D
）
9
,
则由
R
产生的
4.
下列偏序集
( )
能构成格
5.
连通图
G
是一棵树当且仅当
G
中
( )
（
A
）有些边是割边
（
B
）每条边都是割边
（
C
）所有边都不是割边
（
D
）图中存在一条欧拉路径
6.
有
n
个结点
(
n
3
)
，
m
条边的 连通简单图是平面图的必要条件
( )
（
A
）
m
3
n
6
（
B
）
n
3
m
6
（
C
）
m
3
n
6
（
D
）
n
3
m
6
7.
设
P,Q
的真值为
0,R,S
的真值为
1,
则下面命题公式 中真值为
1
的是（
）
（
A
）
R
P
（
B
）
Q
S
（
C
）
P
S
（
D
）
Q
R
8.
在图
G=
中
,
结点总度数与边数的关系是（
）
（
A
）
deg(
v
i
)
2
|
E
|
（
B
）deg(
v
i
)
|
E
|
（
C
）
deg(
v
)
2|
E
|
i
v
V
（D
）
deg(
v
)
|
E
|
i
v
V
9.
设有
33
盏灯
,
拟公用一个电源
,
则至少需有五插头的接线板数（
）
（
A
）７
（
B
）８
（
C
）９
（
D
）１４
10.
设集合
A
上有四个元素
,
则
A
上的不同的等价关系的个数为（
）
（
A
）
11
（
B
）
14
（
C
）
17
（
D
）
15
二、填空题（
每题
2
分，共
20
分
）
1.
设
A={a
，
b
，
c
，< br>d}
，其上偏序关系
R
的哈斯图为
则
R=
。
2.
设
A
{
x
|
x
2
,
n
N
}
，
定义
A
上的二元运算
*
为普通乘法、
除法和加法，
则代数系 统
*>
中运算
*
关于
运
算具有封闭性。
3.
A
，
B
，
C
表示三个集合，文氏图中阴影部分的集合表达式为
。
A
B
C
n
。
4.
矛盾式又叫
式，其定义为
。
5.
的图称为无向图。
第
1
页
/
共
4
页
6.
设
>
是一个偏序集合，在
A
的一个子集中，如果
，则称这个子集为链。
7.
在真值表中，一个公式的真值为Ｆ的指派所对应的大项的合取，即为此公式的
范式。
8.
设
R
是非空集合
A
上的等价关系，对任意的
a
A
，定义
为
a
关于
R
的等价类。
9.
设
是一个群，
A
，
B
∈
P(G)
且
A
≠
，
B
≠
，则
A和
B
的积
AB=
。
10.
的无向图称为树。
三、判断题（
每题
1
分，共
10
分
）
1.
公式
xP
(
x
)
yQ
(
x
,
y
)
的前束范式为
< br>x
y
(
P
(
x
)
Q< br>(
x
,
y
))
。
（
）
2.
(A
B)
C=(A
C)
(B
C)
。
（
）
3.
不存在既对称又反对称的关系。
（
）
4.
若无向连通图
G
中存在桥，则
G
的点连通度 和边连通度都是
1
。
（
）
5.
{{
Ø
}}
{
Ø，
{{
Ø
}}}
。
（
）
6.
任意图结点度数的总和等于边数的两倍。
（
）
7.
设
A
,
,
是布尔代数，则
A
,
,
一定为有补分配格。
（
）
8.
群中有零元。
（
）
9.
质数阶群没有非平凡子群。
（
）
10.
(
x)A(x)
∨
(
x)B(x)
(
x)(A(x)
∨
B(x))
（
）
四、解答题（
3
小题，共
20
分
）
1.
（
5
分）考虑在七天内安排七们功课的考试，使得同一位教师 所任的两们课程考试不安排在接连的两天里，试说明如果没有教
师担任多于四门课程，则符合上述要求的 考试安排总是可能的。
2.
3.
（
8
分）求公式
(Q
P)
∧
P
∧
R
的主析取范式和主合取范式。
4.
（
7
分）已知无向图
G
有
11条边
,2
度与
3
度顶点各
2
个
,
其余 都是
4
度顶点
,
求
G
中共有几个顶点，写出过程。
第
2
页
/
共
4
页