离散数学试题(2008-2-B)

大学期末考试试卷（ B 卷）

2008 学年第 二 学期 考试科目： 离散数学

考试类型：（闭卷） 考试时间： 120 分钟

学号 姓名 年级专业

注意事项：1．考试时间120分钟，闭卷考试

2．试卷共五大题，满分100分

3．全部答案写在答题纸上，试卷纸上答题无效 ．．．．．．．．

一、填空（每空2分，共30分）

1、设P：1+1=2，Q：2是偶数，将命题“1+1=2，仅当2是偶数”符号化 (1)___，其真值为 (2)___。 2、在公式x(F(x,y,z)G(x,y))中，约束出现的变元为 (3)___。 3、给定集合A{1,2,3}上的3个关系如下：

R1{2,2,2,3,2,1,1,1}，R2{2,2,2,3,2,1,3,3,1,1}， R3{2,3,2,2,3,2,1,1}，

则其中满足对称性的关系是 (4)___；满足自反性的关系是 (5)___。 4、非空集合A上的自反、 (6)___和传递的关系称为A上的偏序关系。 5、后缀表达式 3 5 2 － * 7 + 4 / 的值是 (7)___。

6、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中

有 (8)___个悬挂顶点。

7、设G为连通的平面图，有5个面，总度数为14，则G有 (9)___条边，有 (10)___个顶点。 8、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点均为树叶，则T有 (11)___个树叶。 9、设集合S{a,b,c,d,e}，S上的运算定义为：

*abcdeaabcdebbdaadccabcbddcadceedbce 则代数系统S,中单位元是 (12)___，b的右逆元是 (13)___，无右逆元的元素是 (14)___。 10、设运算的运算表如下所示，则运算满足交换律、幂等律、结合律中的 (15)___。

- 1 -

《离散数学》期末考试试卷 2008学年第二学期

* a b c a c a b

b a b c c b c a 二、选择题（每题2分，共30分）

1、下面语句是真命题的为_____。

A、我正在说谎。

B、如果1＋1＝2，则太阳从西边升起来。 C、如果1＋1＝3，则太阳从西边升起来。 D、吃饭了吗？

2、命题公式P→(Q→P)为_____。

A、重言式 B、可满足式 C、矛盾式 D、等值式 3、下面联结词不具有交换律的是_____。

A、∧ B、∨ C、→ D、

4、设I是如下一个解释，D{a,b}，其中p(a,a)，p(b,a)为真，p(a,b)，p(b,b)为假，则在解释I下取真值的公式是______

A、xyp(x,y) B、xyp(x,y) C、xp(x,x) D、xyp(x,y) 5、下列哪个表达式错误_____。。

A、 x(P(x)Q(x))xP(x)xQ(x)

B、 xP(x)xQ(x)x(P(x)Q(x)) C、 x(P(x)Q(x))xP(x)xQ(x) D、 x(P(x)Q(x))xP(x)xQ(x)

6、设集合A{1,2,3,4}上的两个关系R{1,1,2,3,2,4,3,4}，则R具有____。

A、自反性 B、传递性 C、对称性 D、反自反性 7、下述结论错误的是____。

A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。

8、设偏序集（A,）关系R的哈斯图如右所示，若A的子集B{2,3,4,5}，则元素6为B的_____。

A、下界 B、上界 C、最小上界 D、以上都不对 9、以下整数序列，能成为一个简单图的顶点度数序列的是_____。

A、1，2，2，3，4，5 B、2，3，3，4，4，5 C、2，2，3，4，5，6

- 2 -

《离散数学》期末考试试卷 2008学年第二学期

D、1，2，2，3，3，5

10、设图G是有6个顶点的连通图，总度数为16，则从G中删去_____条边后可以使之成为树。

A、10 B、5 C、3 D、2 11、在下列关于图论的命题中，正确的是_____。

A、哈密顿图一定是欧拉图

B、无向完全图Kn(n3)都是欧拉图

C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出 D、哈密顿图是平面图 12、下面编码_____不是前缀码。

A、11，00，10，01 B、01，11，011，1001

C、101，11，001，011，010

D、010，11，011，1011，1001，10101 13、6阶非同构的无向树有_____棵。

A、5 B、6 C、7 D、8 14、实数集R关于下列二元运算满足结合律和交换律的是_____。

A、aba2b B、abb C、abab2ab D、ab|ab| 15、在下列选项中，不是群的是_____。

A、(Q,)，Q为有理数，+为加法运算



B、(R,)，R为非零实数集，为乘法运算

C、(R,)，R为实数集，+为加法运算 D、(Q,)，Q为有理数，*为乘法运算

三、计算题（5分+6分+8分，共19分）

1、求下图中的最小生成树，并计算它的权。

V2 1 V1 3 2 V6 4 6 7 V5 9

2、设有7个字母在通信中出现的频率(%)如下：

a: 35% b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5% (1)以频率(或乘100)为权，求最优2元树． (2)利用所求最优2元树找出每个字母的前缀码．

(3)求传输10000个按上述比例出现的字母需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?节约多少个二进制位？

3、设集合X{a,b,c,d}，X上的关系R如图所示，试求：

- 3 -

5 V3 8 V4 《离散数学》期末考试试卷 2008学年第二学期

a b c d

（1）写出关系R的关系矩阵MR

（2）求关系R的自反闭包r(R)的关系矩阵Mr(R), (r(R)RRRIX) （3）求关系R的对称闭包s(R)的关系矩阵Ms(R), (s(R)RR)

（4）求关系R的传递闭包t(R)的关系矩阵Mt(R), (t(R)RRRR)

23410四、证明题（5分+5分+5分，共15分）

1、设AZZ,在A上定义二元关系R如下：x,y,u,vRxvyu,其中x,y,u,vZ，证明：R是A上的等价关系。

2、设n阶m条边的无向图G中，m=n+1，证明G中存在顶点v：d(v)≥3。 3、设G为群，aG，令H{a|kZ}，证明：H是G的子群。

k五、应用题（共6分）

1. 如果王小红努力学习，她一定取得好成绩。若王小红贪玩或不按时完成作业，她就不能取得好成绩。所以，如果王小红努力学习，她就能按时完成作业。

(1) 将命题中的4个简单命题依次符号化为p,q,r,s； (2) 将命题符号化，即将命题的前提和结论符号化； (3) 在自然推理系统P中构造命题的推理证明。

- 4 -