莆田学院期末考试试卷 （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、(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 页
相关推荐：
loading