-
华南农业大学期末考试试卷（
A 卷）
2011-2012 学年第
一 学期
考试类型：（闭卷）考试
考试科目：
考试时间：
年级专业
离散结构
分钟
120
学号
姓名
题号
一
二
三
四
五
总分
得分
评阅人
□ 林旭东
□ 黄华伟 □ 朱梅阶 □ 黄沛杰
考试注意事项：
①本试题分为试卷与答卷
2 部分。试卷有
五大题，共
4 页。
②所有解答必须写在答卷上，写在试卷上不得分。
一、选择题 （本大题共
10 小题，每小题
2 分，共
20 分）
得分
1、重言式的否定是（
）
A、重言式
B、矛盾式
C、可满足式
D、
A-C
均有可能
2、
A( x)
：
x
在北京工作，
B( x)
：
x
是北京人；则命题“在北京工作的人都是北
京人。”可表示为
______。
A、
xA( x)
B(x)
B、
x( A(x)
B( x))
C、
xA( x)
B(x)
D、
x( A(x)
B( x))
3、设 p:天冷 , q:小王穿羽绒服，下列命题中，和命题“只要天冷，小王就穿羽
绒服。”一样符号化为
p
q 的是 ______。
A 、如果天不冷，则小王不穿羽绒服。
B、小王穿羽绒服仅当天冷的时候。
C、除非小王穿羽绒服，否则天不冷。
装
订
线
D、只有天冷，小王才穿羽绒服
4、下列哪个表达式错误 _____。
A 、
x( A( x) B)
xA( x)
B
B、
x( A( x)
B)
xA( x) B
C、
x( P( x)
Q( x))
xP(x)
xQ( x)
D、
x( P( x)
Q( x))
xP(x)
xQ( x)
5、设
A {1,2,3,...,10}
，定义 A 上的关系
R { x, y | x, y
S x y 10}
，则
R
具有的性质为 ______。
A 、自反的
B、对称的
C、传递的，对称的
D、传递的
6、设V=
为普通乘法，下面函数中是
V 的自同态的是 ______。
A 、 f(x)=2x
B、f(x)= x
C、 f(x)=1/x
D、f(x)=x+1
7、设V=
3
= _____。
A 、-8
B、 8
C、-6
D、 6
8、给定下列各序列，可以构成无向简单图的度数序列为
______。
A 、1,1,2,2,3
B、1,1,2,3,3
C、0,1,1,3,3
D、1,3,4,4,5
9、具有 6 个顶点， 12条边的连通简单平面图中，次数为
3的面有 ______个。
A 、 5
B、 6
C、 7
D、 8
10、在下面所示的 4个图中， ______不是单向连通图。
A 、
B 、
C、
D 、
得分
二、填空 题（本大题共 15 空，每空 2 分，共 30 分）
1、p→ q 的主合取范式是 ____________________。
1
2、表达式
x yA( x, y)
中谓词的个体域是
D { a, b}
，将其中的量词消去，写成与之
等价的命题公式为 __________________。
3、若明天是星期一或星期三，我就有课。若有课，今天必备课。我今天下午备
课。 所以，明天不是星期一和星期三。 将命题中的 4个简单命题依次符号化为，
p：明天是星期一， q：明天是星期三， r：我有课， s：我备课。则推理的 形 式
结 构 为 ： 前 提 ： ______________________________； 结 论 ：
_____________________。
4、
x( yF (x, y)
yG( x, y))
的前束范式为：
____________________。
5 、
设
R ， S 是
集 合
A {1,2,3,4}
上 的 两 个 关 系 ， 其 中
{ 1,1 , 2,2 , 2,3 , 3,2 , 4,4 }
,
R { 1,1 , 2,2 , 2,3 , 4,4 }
，
S
则
(R S)
1
____________________。
6、设偏序集
A,
的哈斯图如右所示，若 A的子集
B
{ 3,4,5}
，
则B的最大下界为 _____。
7、在整数集 Z 上定义二元运算
则关于运算
，
x, y Z
有
x y x y
2
，
的幺元是 ______。
3
8、设 a是12阶群的生成元，则 a是
阶元素
9、若连通平面图 G有 4 个结点， 3 个面，则 G有
10、在右边的 PERT图中，关键路径为 ______。
条边
。
11、一颗带权为 2,3,5,7,8,9的最优 2元树，其权为 ______。
12、1400 的不同的正因子个数为 ______。
13、满足等式
x
1
x
2
x
3
x
4
______。
8
的非负整数解的个数有
14
、
n阶无向树至少有
______
片树叶。（
n>=2
）
得分
三、计算题 ：（ 6+4+6+6，共 22 分）
1、设 A={1, 2, 3, 4} ， R={
A 且x+y<5}
2
装
订
线
（1）写出 R的集合表达式和关系矩阵，画出
R的关系图。
（2）画出关系 R的自反闭包 r(R)、对称闭包 s(R)和传递闭包 t(R)的关系图。
2、分别画出下面无向图 A 的关联矩阵和有向图
B 的邻接矩阵。
v
v
e
1
V
4
1 4
v
1
1
e
5
e
3
e
e
2
e
4
2
3
e
5
4
e
v
2
V
3
v
2
v
3
图 A
图 B
3、求下面带权图中 v
1
到其它顶点的最短路径及对应的权。
v
2
10
v
4
2
3
3
2
6
v
1
4
v
6
4
2
v
3
v
5
4、设有
单位）：
5
个城市
W(v
v
1
, v
2
, v
3
, v
4
,v
5
，任意两城市之间的铁路造价如下（以百万元
为
1
2
1
3
1
4
1
5
W(v ,v
,
W(v , v
v )=4,
W(v ,
v )=7,
W(v , v )=16,
W(v
, v )=10,
)=13,
)=8,
W(v , v )=17,
W(v , v
)=3,
W(v
,v )=10，
2
3
2
4
2
5
3
4
3
5
W(v
4
, v
5
)=12。试求出连接 5 个城市的且造价最低的铁路网。
4 个小题，每题 6 分，共 24
分）
1、用等值演算法证明下面的等值式
(( P
Q )
( P
R))
( P
(Q
R))
2、设 A为整数集合，在 A
A上定义二元关系 R：
<
x+y = u+v，证明： R是 A A 上的等价关系。
3、符号化下列各命题，并说明结论是否有效（用推理规则）
。甲乙丙丁四人
参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜， 如果甲不
获胜，则丁不失败。所以，如果丙获胜，则丁不失败。
4、设
的子群。
五、应用题（共
4 分）
若有 n 个人，每个人都恰有三个朋友，则
n 必为偶数。
华南农业大学期末考试参考答案（
A 卷）
3
四、证明题：（本大题共
-
-
-
-
-
-
-
-
本文更新与2020-11-24 14:05，由作者提供，不代表本网站立场，转载请注明出处：https://www.bjmy2z.cn/gaokao/460619.html