09离散数学期考A卷

2009—2010学年 第 一 学期

数计学院（系）07级计算机应用/教育专业

《离散数学》期末试卷（A）答题纸

注意事项

1、学生的院（系）别、专业、班级、姓名、学号必须填写在考生信息栏内指定的位置。

2、学生在考试之前必须填写考试时间和地点。

3、答题字迹要清楚，并保持卷面清洁。 试卷 共 4 页第 1 页

09离散数学期考A卷

一、选择题(12%)：(每小题2分)

1、命题公式为p→(p∨q∨r)（ A ）。

A．重言式B．可满足式C．矛盾式 D．等值式 2．设集合A = {1，a}，则P(A) =（ C ）。 A．{{1}，{a}} B．{f，{1}，{a}} C．{f，{1}，{a}，{1，a}} D．{{1}，{a}，{1，a}}

3 ．若连通图G V,E ，其中|V| n,|E| m，则要删去G中（ C ）条边， 才能确定G的一棵生成树。

A．n m 1 B．n m 1 C．m n 1 D．m n 1 4 ．S5={0, 1}，*为模2加法，为模2乘法。（ C ）

A．不构成代数系统 B．构成环 C．构成域 D．构成格 5 ．如下图所示各图，其中存在哈密顿回路的图是（ C ）。

A． B． C． D．

6 ．设代数系统(K1, )和(K2, )，存在映射f:K1 K2，如果 a,b K1，都有（ B ）， 称K1与K2同态。

A．f(a b) f(a) f(b) B．f(a b) f(a) f(b) C．f(a b) f(a) f(b) D．f(a b) f(a) f(b)

二、填空题(24%)：(每题3分)

1. 设集合A = {a,b,c,d}，A上的二元关系R = {<a,a>,<a,b>,<b,d>}，S = {<a,d>,<b,c>,<b,d>,<c,b>}，则R·S = ，R 2 = 。

2. 给定平面图G，如下图所示，则G的面数为 4 ，G中面的总次数为 18 。

3. 一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有 个顶点。4.“不存在比所有火车都快的汽车。”在一阶谓词逻辑中符号化为 。

5. 判断函数f：N→N，

6.无向图G如下图所示：求G的支配数γ0= ，边覆盖数α1= ，

匹配数β1= 。

7．设G=<a>是15阶循环群，G的所有的生成元为 。 8．设σ,τ是5元置换,且

将στ,表成不交的轮换之积 。

三、计算作图题(40%) (每小题8分)

1、试求命题公式P Q R的主析取范式和主合/析取范式。

2. 在某次研讨会的休息时间，3 名与会者根据王教授的口音分别作出下述判断：

甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。

丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们 3 人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？

09离散数学期考A卷

3．设集合S的一个关系R={(d，d)，(b，b)，(c，c)，(a，a)，(e，e)，(d，b)，(b，a)，(d，a)，(d，

c)，(c，a)，(c，e)，(d，e)},R是全序关系吗？若存在哈斯图请画出来；若有特殊元存在，请求出： (1) S的极大/极小元，最大/最小元;

(2) 子集B={b，c}的上界、上确界和下界、下确界

.

4．统计得某系列活动的频率分别如下表

编号

a b c d e f g h i j 频率

0.2 0.2 0.06 0.07 0.02 0.01 0.05 0.04 0.3

0.05

用最优二叉树方法将上述10项活动设置成哈夫曼编码以便电子发送。

5. 画出所有5阶和7阶非同构的无向树。

09离散数学期考A卷

四、证明题(24%) (每小题12分)

1．在整数环中定义*和◇两个运算， a,b∈Z 有 a*b=a+b-1, a◇b=a+b-ab。证明Z关于这两个运算构成环。

2. 在自然推理系统F中，证明下面推理（个体域为人类的集合）：

每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。小王是科学工作者，并且是聪明的，所以小王在他的事业中将获得成功。