2021国家开放大学电大本科《离散数学》期末试题及答案（试卷号：1009） 7页

2021 国家开放大学电大本科《离散数学》期末试题及答案（试卷号：1009 ） 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 得分 评卷人 一、单项选择题（每小题 1 分，本题共 20 分） B. 任一整数 z 对任意整数；y 满足 z+y = 0 C. 存在一整数］对任意整数 w 满足 z+v = 0 D. 对任一整数］存在整数）满足 z+y=0 U.将语句“3 大于 2 或 1 加 1 等于 2”翻译成命题公式. 12. 将语句“他们明天去旅游，仅当明天天晴.”翻译成命题公式. 得分 评卷人 二、判断题(每小题 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) 得分 评卷人 三、逻辑公式翻译(每小题 6 分，本题共 12 分) 四、计算题(每小题 12 分，本题共 48 分) 13. 设集合 A = {1,2,3},B = {2,3,4},C={2,<3}},试计算： (DA-C；(2)AnB；(3)(AnB)XC. 14 .设偏序集的哈斯图如图一所示，B 为 A 的子集，其中 B = {a,6,c},试: 图一 (1) 写出 R 的关系表达式； (2) 画出关系 R 的关系图； (3) 求出 B 的最大元、极小元、最小上界. 15. 图 G = ，其中 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 分） （3）（AC1B）XC={V2,2>,V2,{3}>,V3,2>,V3,{3}>}. （12 分） 14. （l）R = {,,b>,,,V5,d>,Vc,Q>}. （4 分） （2）关系图如图二所 7K : 图二 （3）集合 B 无最大元、极小元为。、最小上界为 d. （8 分） （12 分） 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}； 4. A 5.D 9. A 10. B （2 分） （6 分） （2 分） （6 分） （4 分） （8 分） 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 分）最小生成树的权 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）主合取范式 （12 分） （2 分）（5 分）（7 分）（9 分）（11 分）（12 分）