离散数学试题2018模拟2+答案 下载本文

华南理工大学网络教育学院

2015–2016学年度第一学期期末考试 《 离散数学 》试卷(模拟卷2)

教学中心: 专业层次:

学 号: 姓 名: 座号: 注意事项:1. 本试卷共 三 大题,满分100分,考试时间90分钟,闭卷;

2. 考前请将以上各项信息填写清楚;

3. 所有答案必须做在答题纸上,做在试卷、草稿纸上无效; 4.考试结束,试卷、答题纸、草稿纸一并交回。

一、单项选择题(本大题30分,每小题6分) A CABC 1 A.如果天气好,那么我去散步。 B.天气多好呀!

C.x=3。 D.明天下午有会吗? 在上面句子中( )是命题

2.设个体域为整数集,下列真值为真的公式是( ) A.?y?x (x – y =2) B.?x?y(x – y =2) C.?x?y(x – y =2) D.?x?y(x – y =2)

3. 设A={0,1},B={1,2},则A×{1}×B=( )

A.{<0,1,1 >,<1,1,1 >,<0,1,2 >,<1,1,2 >} B.{<0,1 >,<1,1 >,<0,2 >,<1,2 >}

C.{<1,0, 1 >,<1,1,1 >,<1,0, 2 >,<1,1,2 >} D.{<0,1,1 >,<1,1,1 >,<0,2, 1 >,<1,2,1 >}

4.设A={1,2,3,4,5, 6},B={a,b,c,d,e},以下哪个函数是从A到B的满射函数( )

A.F ={<1,b>,<2,a>,<3,c>,<1,d>,<5,e>, <6,e>} B.F={<1,c>,<2,a>,<3,b>,<4,e>,<5,d>, <6,e>} C.F ={<1,b>,<2,a>,<3,d>,<4,a>, <6,e>}

D.F={<1,e>,<2,a>,<3,b>,<4,c>,<5,e>, <6,e>} 5.对于群来说,下列判断错的是( )

A.群中除了幺元外,不可能再有等幂元 B.群与其子群共一幺元 C.循环群的生成元是唯一的

D.任何一个循环群必定是阿贝尔群

《 离散数学 》 第 1 页 (共 2 页)

二、 判断题(本大题20分,每小题4分) ×××√×

1、命题公式(P?Q)?(?R?T)是析取范式。 ( ) 2、设c是个体域中某个元素,A是谓词公式,则A(c)? ?xA(x)。 ( ) 3.集合A 的幂集P(A)上的包含关系是偏序关系。 ( ) 4.任何图都有一棵生成树。 ( ) 5.连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 ( )

三、解答题(计算或者证明题:本大题50分,每小题10分) 1.设命题公式为(P ?(P? Q))? Q。 (1)求此命题公式的真值表; (2)判断该公式的类型。 解 (1) 真值表如下 P 0 0 1 1 Q P?Q P ?(P? Q) 0 1 0 1 1 0 0 0 0 1 1 1 (2)该公式为重言式 (P ?(P? Q))? Q 1 1 1 1

2.用直接证法证明

前提:P ? (Q ? R),S ? ? Q,P,S。 结论:R

证 (1)P P (2) P ? (Q ? R) P

(3) Q ? R T(1,2)I (4)S P (5) S ? ? Q P

(6)?Q T(4,5)I (7) R T(3,6)I

3.设R是集合A = {1, 3,4, 5,8,12,24}上的整除关系。

(1) 给出关系R; (2) 给出COV A

(3) 画出关系R的哈斯图;

(4) 给出关系R的极大、极小元、最大、最小元。

《 离散数学 》 第 2 页 (共 2 页)

解 R={<1,3>,<1,4>,<1,5>,<1,8>,<1,12>,<1,24>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<8,24>,<12,24>}∪IA

COV A={<1,3>,<1,4>,<1,5>,<3,12>, <4,8>,<4,12>,,<8,24>,<12,24>} 作哈斯图如右上:

由图看出该偏序集没有最大元,最小元为1;5,24是极大元,1是极小元和最小元。

248415123

4.如图所示带权图,用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值。

13245

C?T??1?3?4?5?2?15

5、给定权为1,9,4,7,3;构造一颗最优二叉树。

解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

241583497W?T??4?1?4?3?3?4?2?7?1?9?51

41《 离散数学 》 第 3 页 (共 2 页)