当前位置:文档之家› 离散数学-期末考试卷-A卷

离散数学-期末考试卷-A卷

离散数学-期末考试卷-A卷
东莞理工学院城市学院(本科)试卷(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,a>,<b,b>,<a,b>,<b,a>},则R具有( )
A. 自反性
B. 反自反性
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 =_______________,A B=________________。

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,那么复合函数))(
fο=__________,
(x
g
f
(x
gο=__________。

)
)(
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、求(﹁P∨Q)→(R∧﹁Q)的主析取范式和主合取范式。

2、已知集合A={1, 2, 3, 4, 5, 6, 8, 12, 18, 21, 24, 36},R是A上的整除关系,求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卷第 11 页共6页。

相关主题