[精选资料]华南农业大学 离散数学 期末考试试卷及答案

华南农业大学期末考试试卷（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、除非小王穿羽绒服，否则天不冷。

1

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)

10}，定义A上的关系R?{?x,y?|x,y?S?x?y?10}，则R5、设A?{1,2,3,...,具有的性质为______。

A、自反的 B、对称的 C、传递的，对称的 D、传递的 6、设V=是代数系统, R*为非零实数的集合，?为普通乘法，下面函数中是V 的自同态的是______。

A、f(x)=2x B、f(x)= ?x C、 f(x)=1/x D、f(x)=x+1

7、设V=是代数系统, Z为整数的集合，+为普通加法在，则 (?2)?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 的主合取范式是____________________。

2

得分 装订线 1.5CM

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}上的两个关系，其中

R?{?1,1?,?2,2?,?2,3?,?4,4?}，S?{?1,1?,?2,2?,?2,3?,?3,2?,?4,4?},

则(R?S)?1?____________________。

6、设偏序集?A,??的哈斯图如右所示，若A的子集B?{3,4,5}，则B的最大下界为_____。

7、在整数集Z上定义二元运算?，?x,y?Z有x?y?x?y?2，则关于运算? 的幺元是______。

8、设a是12阶群的生成元，则a3是 阶元素

9、若连通平面图G有4个结点，3个面，则G有 条边。 10、在右边的PERT图中，关键路径为______。 11、一颗带权为2,3,5,7,8,9的最优2元树，其权为______。 12、1400 的不同的正因子个数为______。

13、满足等式x1?x2?x3?x4?8的非负整数解的个数有______。

14、n阶无向树至少有______片树叶。（n>=2）

得分 三、计算题：（6+4+6+6，共 22 分）

1、设A={1, 2, 3, 4}，R={|x?A，y?A且x+y<5}

3

（1）写出R的集合表达式和关系矩阵，画出R的关系图。

（2）画出关系R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的关系图。 2、分别画出下面无向图A的关联矩阵和有向图B的邻接矩阵。

e1 e2 v1 e3 v2 图A

V4 e4 e5 V3 e1 v1

e2

e3 e4

v4

e5 v3

图B

v2

3、求下面带权图中v1到其它顶点的最短路径及对应的权。

v2 3 10 6 4 3 2 v4 2 2 4 v1 v3 v6

v5

4、设有5个城市v1,v2,v3,v4,v5，任意两城市之间的铁路造价如下（以百万元为单位）：W(v1, v2)=4, W(v1, v3)=7, W(v1, v4)=16, W(v1, v5)=10, W(v2,v3)=13, W(v2, v4)=8, W(v2, v5)=17, W(v3, v4 )=3, W(v3 ,v5)=10， W(v4, v5)=12。试求出连接5个城市的且造价最低的铁路网。 四、证明题：（本大题共 4 个小题，每题 6 分，共 24 分） 1、用等值演算法证明下面的等值式

((P?Q)?(P?R))?(P?(Q?R))

2、设 A为整数集合，在 A?A上定义二元关系R：

<,>?R ? x+y = u+v，证明：R是A?A上的等价关系。 3、符号化下列各命题，并说明结论是否有效（用推理规则）。甲乙丙丁四人

4

装订线 1.5CM

参加拳击比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。

4、设是群，给定a∈G，令H={y? y*a=a*y, y∈G}，证明：是G的子群。 五、应用题（共4分）

若有n个人，每个人都恰有三个朋友，则n必为偶数。

华南农业大学期末考试参考答案（A卷）

一、选择题（本大题共 10 小题，每小题 2 分，共 20 分） 得分

1 B 2 D 3 C 4 C 5 B 6 C 7 D 8 B 9 D 10 C

二、填空题（本大题共 15 空，每空 2 分，共 30 分） 得分

1、 ?p∨q ； 2、(A(a,a)?A(a,b))?(A(b,a)?A(b,b))； 3、 (p∨q)→r, r→s, s ； ?p∧ ?q ；4、?x?y?z(F(x,y)?G(x,z))； 5、{?1,1?,?2,2?,?2,3?,?3,2?,?3,3??4,4?}； 6、 2 ；7、 2 ； 8、 4 ； 9、 5 ； 10、v1v3v7v8；

11、 83 ； 12、 24 ； 13、 165（或C8311，或C11） 14、 2

三、计算题：（6+4+6+6，共 22 分） 得分 1、 R的集合表达式：

R?{?1,1?,?1,2?,?1,3?,?2,1?,?2,2?,?3,1?}

R的关系矩阵: R的关系图：

5