中国计量学院_2009-2010第一学期离散数学试卷A

中国计量学院 200 9

~ 2010 学年第 1 学期

《 离散数学 》课程考试试卷(A)开课二级学院：理学院 ，考试时间：2010 年 1 月 6 日 14:00-16:00 时 入场 专业： 四 五 六 班级： 七 总分

考试形式：闭卷√、开卷□,允许带 考生姓名： 题序 得分装

学号： 一 二 三

评卷人

一. 选择题： (每题 3 分，共 15 分) 1. 设命题公式 G: ( p q) ( r q) ,则使公式 G 取真值为 1 的 p,q,r 赋值分别是

( (B)0,0,1 (C)1,0,1 (D)1,0,0 ( (B) (p∨┐p)→q (D) p→┐q ((B) p ( p q), p ( p q) (D) p ( p q), q

) )

(A)0,0,0

2. 下列是重言式的为订

(A) p→ (p∨q) (C) q∧┐q 3. 下列命题公式等值的是(A) p q, p q (C) q ( p q), q p q

)

4. 下列数组中，能构成无向图的度数列的数组是 (A) (1, 1, 2, 3) (B) (D) (1, 2, 3, 4, 5) (1, 3, 3) (C) (2, 2, 2, 2) 5. 集 合 X={0,1,2,3}线

(

)

, R 是 X 上 的 二 元 关 系 ， R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>},则 R 的关系矩阵 M R 是( )

1 1 A. 0 0

0 1 0 0

1 0 0 1

0 0 1 1

1 0 B. 1 0

0 0 1 0

1 1 0 0

0 1 0 1

0 1 C. 0 1

0 0 1 1

0 1 0 1

1 0 1 0

1 0 D. 0 1

1 0 0 0

1 1 0 1

0 1 1 0 4 页

中国计量学院 200 9 ~~~2010 学年第

1 学期《

离散数学

》课程试卷( A )第 1 页 共

二． 填空题（每空2分，共20分）

1.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为 2. 判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一

的 。

3.设 X={a, b, c, d} , Y={1, 2, 3, 4, 5}, f={<a,1>, <b,3>, <c,4>, <d,4>},

则domf=_____________ ，ranf=________________ .

4. 有向图D的度数列为（2，3，2，3），出度列为（1，2，1，1），则此图的入度列为

_______________

5. 已知无向图G中有1个1度结点，2个2度结点，3个3度结点，则G的边数

是 ．

6. 在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______． 7.设T是各边带权均为1的n阶带权图的一棵最小生成树，则W(T) ___________.

三．计算题（本题12分）

求命题公式p ((q r) (p ( q r)))的主析取范式。

．

中国计量学院200 9 ~2010 学年第 1 学期《 离散数学 》课程试卷（ A ）第 2 页 共 4 页

四. (本题 10 分)在自然推理系统 P 中构造下面推理的证明:前提: ( p q), q r , r 结论: p

装

五. (本题 10 分)一棵树有 2 个 4 度结点，3 个 3 度结点，其余结点是叶子，求该树的叶子数。

订

六. (本题 13 分)设有向图 G=(V,E)如下图

所示，试用邻接矩阵方法求长度为 2 的路的总数和回路总数。

线

中国计量学院 200 9 ~~~2010 学年第

1 学期《

离散数学

》课程试卷( A )第 3 页 共

4 页

七．（每题10分，共20分）

（1）设S={a，b}，*是S上二元运算，满足

a*b=b*b=b，a*a=b*a=a 证明<S,*>为半群

（2）在通信中,设八进制数字出现的频率(%)如下: 0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 5 采用2元前缀码, 求传输数字最少的2元前缀码, 画出最优树，并求传输100个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的 (长为3) 的码字传输需要多少个二进制数字?

中国计量学院200 9 ~ 20 10 学年第 1 学期

《 离散数学 》课程 试卷（ A ）参考答案及评分标准

开课二级学院： 理学院 ，学生班级： 08计算机1，2,3班 ，教师： 尚绪凤

一．选择题：（每题3分，共15分） 1．C 2. A 3. C 4. C 5. B

二. 填空题（每空2分，共18分） 1. P∧┐Q

2. 陈述句 真值

3. X或{a,b,c,d} {1,3,4} 4. （1，1，1，2） 5. 7

中国计量学院200 9 ~2010 学年第 1 学期《 离散数学 》课程试卷（ A ）第 4 页 共 4 页

6. 0 1 7. n-1

三．计算题（本题12分）

求命题公式p ((q r) (p ( q r)))的主析取范式。

解：

p ((q r) (p ( q r) p ((q r) (p (q r)))……….…2分

p ((p q r) 0) ……………………………..…..………4分

p p 1 1 p (q q) (r r) … ……………………………….6分

( p q r) ( p q r) ( p q r) ( p q r)………...8分

m1 m2 m3 m7 ……………………………………….…..10分

p ((q r) (p ( q r) m0 m1 m2 m3 m7…………..…………….12分

四．（本题10分）在自然推理系统P中构造下面推理的证明:

前提: (p q),q r,r 结论: p

证明:

(1) q r 前提引入

(2) r 前提引入

(3) q (1)(2)拒取式………..……………. 3分 (4) (p q) 前提引入

(5) p q (4)置换 ………..……… ……...3分

(6) p (3)(5)析取三段论…..………………………10分

五．（本题10分）一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子

数。

解：设叶子数有x个，则该树有2+3+x=5+x个结点，有5+x-1=4+x条边。

（4 分）

由握手定理

中国计量学院200 9 ~2010 学年第 1 学期《 离散数学 》课程试卷（ A ）第 5 页 共 4 页

2*4+3*3+x*1=2（4+x）

解得 x=9 ，故有9个叶子。 .10分

六．（本题13分）

设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。

1100 1010

解：M= （3 分）

1011 0011 2 2 2

M=

2 1

110

111

（6 分）

121 011

i 1j 1

44

M2ij

18,

M

i 1

4

2

ii

6 （10 分）

G中长度为2的路总数为18，长度为2的回路总数为6。 (13 分)

七．（本题20分）

（1）设S={a，b}，*是S上二元运算，满足

a*b=b*b=b，a*a=b*a=a 证明<S,*>为半群。

证明：a*b=b*b=b∈S，a*a=b*a=a∈S，

所以*在S上是封闭的。 （4 分） 又设任意a,b,c∈S 有

a*（b*c）=a*c=c， c=b*c=（a*b）*c 即 a*（b*c）= （a*b）*c

所以*在S上是可结合的。 …… 此处隐藏：1994字，全部文档内容请下载后查看。喜欢就下载吧 ……