20112 离散数学期末试卷试卷A(计算机102、计教101)

莆田学院期末考试试卷 （A）卷

2011 —— 2012 学年第 二 学期

课程名称： 离散数学B 适用年级/专业： 计教101、计算机102 试卷类别 开卷（ ）闭卷（√） 学历层次 本科 考试用时 120 分钟

《考生注意：答案要全部抄到答题纸上，做在试卷上不给分》 ．．．．．．．．．．．．．．．．．．．．．．．．．．．一、简答题(共10分)

1、(4分) 用数理逻辑的方法讨论下面的推理是否正确：

如果今天是星期日，则明天是星期一；明天是星期一。所以今天是星期日。 2、(6分)已知命题公式A中含3个命题变项p,q,r，并知道它的成真赋值分别为 010，101，111。求A的主合取范式。 2、(6分) 答：

此时可知成假赋值０００，,００１,０１１,１００,１１０， ‥‥‥‥‥‥(2分)

则它的主合取范式

(p?q?r)?(p?q??r)?(p??q??r)?(?p?q?r)?(?p??q?r)

?M000?M001?M011?M100?M110?M0?M1?M3?M4?M6 ‥‥‥‥‥‥(4分)

二、判定题(共20分)

1、(12分)下述给定的图形中，

(1) 哪些不可一笔画？简述理由。 ．．

(2) 哪些是哈密顿图？简述理由；对不是哈密顿图的指出至少加多少边，使其成为哈

试卷第 1 页 共 6 页

密顿图。

(3) 哪些是平面图？并将其平面表示。 (4) 哪些是二部图？简述理由。

2、(3分) 已知有向图如下，判定其连通性，简述理由。

3、(5分)设A?{1,2,3}上的关系如下图，判定它具有的关系，简述理由。

3、(5分)

答：具有反对称 传递；有的顶点有环，有的顶点没有环，所以没有自反性，也没有反自反性；不同顶点的有向边是单向的，没有对称性。 ‥‥‥‥‥‥(5分)

三、画图题(共15分)

1、(6分) 设A={2,3,4,5,6,7,8,9,10,12,20}，R为整除关系，

(1) 画出偏序集的哈斯图； (2) 指出该偏序集的极大元和极小元。

2、(9分) 在下列两个正整数数列中，哪个（些）能充当无向树的度数列？若能，请画出2棵非同构的无向树。 (1) 1,1,1,1,2,3,3,4 (2) 1,1,1,1,,2,2,3,3 2、(9分)

解：(1) 从（1,1,1,1,2,3,3,4）知

?d(v)?4?2??3?3?4?16 ?2(8试卷第 2 页 共 6 页

不满足无向树的必要性：m?n?1，所以不能充当任何无向树度数列。‥‥‥(3分)

(2) 可以, ‥‥‥‥(3分)

并且有很多满足其度数列为（1,1,1,1,2,2,3,3）的不同构的无向树。如

‥‥‥(3分)

四、计算题(共30分)

1、(6分) 有向图D如左图所示,它的邻接矩阵为A

其中

??1200??220??3222??564A??0010???1210?22?，A21001?3?1001????1210???，A??1?2221???，A4??2?443?0010????1001????1210????222计算

(1) D中从v3到v2的长度为小于或等于4的通路数目。 (2) D中长度为小于或等于4的回路数目。

2、(12分) 已知对应于权2,2,3,3,5的三棵二叉树T1,T2,T3如下，

试卷第 3 页 共 6 页

2?1?2?? 1??(1) 请计算它们的权，写出每棵树所确定二元前缀码。 (2) 并判断其中是否为最佳前缀码？有对应的最优二叉树？ (3) 如果其中没有最佳前缀码，请计算出最佳前缀码。

3、(12分)假设某学院学生本学期的公共选修课的选课情况如下：260人选修艺术类课程，208人选修人文类课程，160人选修理工类课程，76人同时选修艺术类与人文类课程，48人同时选修艺术类与理工类课程，62人同时选修人文类与理工类课程，全部三类课程都选的有30人，三门都不选的有150人，问： (1) 该学院共有多少名学生？

(2) 有多少名学生选修人文类课程，但不选艺术类或理工类课程？ 五、证明题(共25分)

1、(13分)在自然推理系统F中，证明下面推理：

每个计算机工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。张明是计算机工作者，并且是聪明的，所以张明在他的事业中将获得成功。(个体域为人类集合) 1、(13分)

B(x):x是刻苦钻研的，C(x):x是聪明的人，D(x):x证明：设A(x):x是计算机工作者，

在他的事业中将获得成功，a:张明 ‥‥‥‥‥‥(3分)

前提：?x(A(x)?B(x))，?x((B(x)?C(x))?D(x))，A(a)?C(a)，

结论：D(a) ‥‥‥‥‥‥(3分)

证明（1）A(a)?C(a) 前提 （2）A(a) （1），化简 （3）?x(A(x)?B(x)) 前提 （4）A(a)?B(a) （3），UI规则 （5）B(a) （2），（4）假言推理 （6）C(a) （1），化简

试卷第 4 页 共 6 页