2021国家开放大学电大本科《离散数学》期末试题及答案.docx

2021国家开放大学电大本科《离散数学》期末试题及答案（试卷号：1009 ）
得分评卷人
、单项选择题（每小题4分，本题共20分）
1. 若集合A = {1,2,3,4},则下列表述正确的是（ ）.
A. {1,2}€A B. {1,2,3}QA
C. {1,2,3}ZDA D. {1,2,3}£A
2. 若集合A的元素个数为5,则其慕集的元素个数为（ ）.
A. 5 B. 16
C. 32 D. 64
3. 若图 G = VV,E＞，其中 V=S,6,c,d},E={（o,6）,0,c）,（b,d）},则该图中的割点 为（）.
A. a B. b
C・ c D. d
4. 无向图G是棵树，结点数为10,则G的边数是（ ）.
A. 9 B. 10
C. 11 D. 12
5. 设个体域为整数集，则公式（Vz）（my）Cz+：y = 0）的解释可为（ ）.
A. 存在一整数1有整数v满足z +、= 0
B. 任一整数z对任意整数；y满足z+y = 0
C. 存在一整数］对任意整数w满足z+v = 0
D. 对任一整数］存在整数）满足z+y=0
得分评卷人
二、判断题(每小题4分，本题共20分)
6. 设N、R分别为自然数集与实数集，/;N->R,/(^)=x + 6,则f是单射.( )
A.正确 B.错误
7. 设G是一个无向图，结点集合为V,边集合为E,则G的结点度数之和为|E|.( )
A.正确 B.错误
8. 有〃个结点的无向完全图K”的边数为〃(〃一 1).( )
A.正确 B.错误
9. 设G是具有〃个结点m条边力个面的连通平面图，则有关系式：〃+4—2 =洲.( )
A.正确 B.错误
10. 设个体域D = {a,b,c},则谓词公式(Vz)A(z)消去量词后的等值式为AG) VA3)
VA(c).( )
A.正确 B.错误
.
得分评卷人
三、逻辑公式翻译(每小题6分，本题共12分)
U.将语句“3大于2或1加1等于2”翻译成命题公式.
12. 将语句“他们明天去旅游，仅当明天天晴.”翻译成命题公式.
得分评卷人
四、计算题(每小题12分，本题共48分)
13. 设集合 A = {1,2,3},B = {2,3,4},C={2,<3}},试计算： (DA-C；(2)AnB；(3)(AnB)XC.
14 .设偏序集<A,R >的哈斯图如图一所示，B为A的子集，其中B = {a,6,c},试:

图一
(1) 写出R的关系表达式；
(2) 画出关系R的关系图；
(3) 求出B的最大元、极小元、最小上界.
15. 图 G = <V,E>，其中 V=〈a ,b ,c ,d ,e> ,E=〈(a ,b) ,c) ,e) ,(b ,(b ,e),
(c,d),(c,e),(d,e)},对应边的权值依次为 2、1、2、3、6、4、1 及 5,试：
(1) 画出G的图形；
(2) 求出G权最小的生成树及其权值.
16. 求P-(Q AR)的合取范式与主合取范式.
试题答案及评分标准
-、单项选择题（每小题4分，本题共20分）
I. B 2. C 3. B
二、 判断题（每小题4分，本题共20分）
6. A 7. B 8. B
三、 逻辑公式翻译（每小题6分，本题共12分）
II. 设P：3大于2,Q：1加1等于2.
则命题公式为：PVQ.
12. 设P：他们明天去旅游,Q：明天天晴.
则命题公式为：P-Q.
四、 计算题（每小题12分，本题共48分）
13. （1）A-C=（1,3）；
（2）AC|B = {2,3}；
4. A 5.D
9. A 10. B
（2分）
（6分）
（2分）
（6分）
（4分）
（8分）

（3）（AC1B）XC={V2,2>,V2,{3}>,V3,2>,V3,{3}>}. （12 分）
14. （l）R = {<a ,q>,<jb,b>,b>,<ja ,c>,<a,d>,V5,d>,Vc,Q>}.
（4分）
（2）关系图如图二所7K :

图二
（3）集合B无最大元、极小元为。、最小上界为d.
（8分）
（12 分）

15. （1）G的图形如图三所示:

图三
（4分）

（2）用Kruskal算法求最小生成树的步骤为:
,c） = 1 ,选（q ,c）
tv（c ,e） = 1,选（c ,e）
w（a,6） = 2,选（"）
w（A,d） = 3,选。M）
最小生成树如图四所示：
图四

（9分）
（12 分）
（2分）
（5分）
（7分）
（9分）
（11 分）
（12 分）

最小生成树的权C（T） = l + l + 2 + 3 = 7.
注：用破圈法求最小生成树参照评分
16. P—（QAR）
AP V（QAR）
0（「PVQ）A（「FVR）合取范式
U（「FVQ）V （时「R） ALFVR）
VQ） V（R A "） AOPVR） V（QA「Q）
0（「P VQVR） A（「P VQV -^）A（-PV^VQ）A（-PV^V-Q）
0（「PVQVR）A（「PVQV」R）A（「PV「QVR）主合取范式