《离散数学-期末考试卷-a卷》由会员分享，可在线阅读，更多相关《离散数学-期末考试卷-a卷（6页珍藏版）》请在金锄头文库上搜索。
1、东莞理工学院城市学院（本科）试卷（A卷）2013-2014学年第一学期开课单位：计算机与信息科学系 ，考试形式： 闭 卷，允许带 入场科目： 离散数学 ，班级：软工本2012-1、2、3 姓名： 学号： 题序一二三四总 分得分A评卷人一、单项选择题（每小题2分，共20分）在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。1. 下述不是命题的是( )A. 做人真难啊! B. 后天是阴天。C. 2是偶数。 D. 地球是方的。2. 命题公式P(PQR)是( )A. 永假的 B. 永真的C. 可满足的 D. 析取范式3. 命题公式BA等价于( )A. AB B. (AB)C.
2、 AB D. AB4设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）APQBPQCPQDPQ5设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）Ax(A(x)B(x)B x( A(x) B(x) )C x( A(x)B(X)D x( A(x) B(x) )6. 设有A=a,b,c上的关系R=,，则R具有( )A. 自反性 B. 反自反性C. 传递性D. 反对称性7. 设A=1,2,3,4,5,6,B=a,b,c,d,e，以下哪一个关系是从A到B的满射函数( ) A. f=,B. f=, C. f=, D. f=,8设简单图G所有结点的度数之和为1
3、0，则G一定有（）A3条边B4条边C5条边D6条边9下列不一定是树的是（）A每对结点之间都有通路的图B有n个结点，n-1条边的连通图C无回路的连通图D连通但删去一条边则不连通的图10下列各图中既是欧拉图，又是哈密顿图的是（）A B C D二、填空题（每空2分，共20分）请在每小题的空格中填上正确答案。错填、不填均无分。1、设A=1, 2, 3, 4，B=2, 3, 5，则A -B =_，AB=_。2、设A=(1,2),(2,4),(3,3),B=(1,3),(2,4),(4,2),那么dom(AB)=_, ran(AB)= _（说明：dom指R的定义域，ran指R的值域）。3、设A=1，2，3
4、，4上关系R=(1,2),(2,4),(3,3),(1,3)，则R的自反闭包r (R)= _，对称闭包s (R)=_。4、设f: RR, f(x)=x2-2, g: RR, g(x)=x-1,那么复合函数=_，=_。5、设A=a,b,c，则A的幂集P(A)= 。6、设A=a, b, c，R是A上的二元关系R=(a, b), (b, c), (c, a)，则其传递闭包为t (R)=。三、计算题（每小题8分，共48分）要求写出详细计算过程，按步给分。1、求(PQ)(RQ)的主析取范式和主合取范式。2、已知集合A=1, 2, 3, 4, 5, 6, 8, 12, 18, 21, 24, 36，R是A
5、上的整除关系，求R的哈斯图。3、设A=1，2，3，4，R是A上的二元关系，R=(1,1), (1,2), (2,3), (3,2) (3,3), (4,1), (4,2), (4,3)。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、反对称、传递性质，并给出理由。4、求出下图的最小生成树并计算该树的权（要求画出最小生成树的形成过程）。5、已知一算式的树(如图)，试分别写出前序周游算法、中序周游算法和后序周游算法的算式。6、画出树叶权为3, 5, 8, 10, 12, 15, 18, 22的哈夫曼树，计算出该最优树的权，并给出哈夫曼编码。四、证明题（共12分）用命题逻辑推理方法证明下面推理的有效性：如果体育馆有球赛，青年大街交通就拥挤。在青年大街交通拥挤情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。 矮化砧嫁接的苹果树树冠体积小于乔化砧嫁接的苹果树树冠体积，矮化砧苹果树单株产量低于乔化砧苹果树，所以，栽植矮化苹果树必须根据不同的矮化砧木和不同类型的短枝型品种适当加大栽培密度离散数学A卷 第 5 页 共6页
