离散数学 期末考试卷 A卷
- 格式：doc
- 大小：68.00 KB
- 文档页数：6
《离散数学》A卷 第 1 页 共6页
东莞理工学院城市学院（本科）试卷（A卷）
2013-2014学年第一学期
开课单位：计算机与信息科学系 ，考试形式： 闭 卷，允许带 入场
科目： 离散数学 ，班级：软工本2012-1、2、3 姓名： 学号：
题序 一 二 三 四 总 分
得分
A评卷人
一、单项选择题（每小题2分，共20分）
在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。
1. 下述不是命题的是( )
A. 做人真难啊! B. 后天是阴天。
C. 2是偶数。 D. 地球是方的。
2. 命题公式P→(P∨Q∨R)是( )
A. 永假的 B. 永真的
C. 可满足的 D. 析取范式
3. 命题公式﹁B→﹁A等价于( )
A. ﹁A∨﹁B B. ﹁(A∨B)
C. ﹁A∧﹁B D. A→B
4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（ ）
A．P∧Q B．P∧Q C．P→Q D．P∨Q
5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（ ）
A． x(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={
A. 自反性 B. 反自反性 《离散数学》A卷 第 2 页 共6页 C. 传递性 D. 反对称性
7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( )
A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>}
B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>}
C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>}
D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>}
8．设简单图G所有结点的度数之和为10，则G一定有（ ）
A．3条边 B．4条边 C．5条边 D．6条边
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(A∪B)=___________________,
ran(A∩B)= __________________（说明：dom指R的定义域，ran指R的值域）。
3、设A={1，2，3，4}上关系R={(1,2),(2,4),(3,3),(1,3)}，
则R的自反闭包r (R)= _____________________________________________________，
对称闭包s (R)=________________________________________________________。
4、设f: R→R, f(x)=x2-2, g: R→R, g(x)=x-1,那么复合函数))((xgf=__________，))((xfg=__________。
5、设A={a,b,c}，则A的幂集P(A)= 。 《离散数学》A卷 第 3 页 共6页 6、设A={a, b, c}，R是A上的二元关系R={(a, b), (b, c), (c, a)}，则其传递闭包为t (R)= 。
三、计算题（每小题8分，共48分）
要求写出详细计算过程，按步给分。
1、求(﹁P∨Q)→(R∧﹁Q)的主析取范式和主合取范式。
2、已知集合A={1, 2, 3, 4, 5, 6, 8, 12, 18, 21, 24, 36}，R是A上的整除关系，求R的哈斯图。
《离散数学》A卷 第 4 页 共6页 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、求出下图的最小生成树并计算该树的权（要求画出最小生成树的形成过程）。
《离散数学》A卷 第 5 页 共6页 5、已知一算式的树(如图)，试分别写出前序周游算法、中序周游算法和后序周游算法的算式。
6、画出树叶权为3, 5, 8, 10, 12, 15, 18, 22的哈夫曼树，计算出该最优树的权，并给出哈夫曼编码。
《离散数学》A卷 第 6 页 共6页 四、证明题（共12分）
用命题逻辑推理方法证明下面推理的有效性：
如果体育馆有球赛，青年大街交通就拥挤。在青年大街交通拥挤情况下，如果小王不提前出发，就会迟到。因此，小王没有提前出发也未迟到，则体育馆没有球赛。
