国开大学2018年01月1009《离散数学(本)》期末考试参考答案.pdf

1、试卷代号:1009座位号rn国家开放大学(中央广播电视大学)2017年秋季学期开放本科期末考试离散数学(本)试题(半开卷)2018年1月曰五四一分一一-吕U一j 六一一一、单项选择题(每小题3分，本题共15分)1.设A=1，2，3，4，B=2，3，剖，A到B的关系R=I x E A，yB.且z十y=5，则R=().A.,B.,C.,.D.,2.若集合A=怡，b,c，d，则下列表述正确的是().A.A B.A C.怡，b,c，dA D.，bCA 3.设个体域为整数集，则公式(V x)(:3 y)(x-y=2)的解释可为().A.存在一整数z有整数y满足x-y=2B.存在一整数z对任意整数y满足x

2、-y=2C.对任一整数z存在整数y满足x-y=2D.任一整数z对任意整数y满足x-y=24.n阶元向完全图Kn的边数及每个结点的度数分别是().A.n(n一1)与nC.n-1与nB.n(n-1)与n一1D.n(n-1)/2与n一15.设G为连通无向图，则()时，G中存在欧拉回路.A.G不存在奇数度数的结点B.G存在一个奇数度数的结点C.G存在两个奇数度数的结点D.G存在偶数度数的结点99|得分|评卷人|I I 二、填空题每小题3分，本题共15分6.设集合A=xlx是小于4的正整数，用集合的列举法A=一一-7.设A=1，2，B=怡，b，C=1，2，从A到B的函数f=，从B到C的函数g=，则复合函

3、数gof=8.设G=是一个圈，结点度数之和为30，则G的边数为一一一一一9.设G是具有n个结点m条边h个面的连通平面图，则n+k一2=一一一一一10.设个体域D=2，3，的，A(x)为x小于3，则谓词公式(Vx)A(x)的真值为|得分|评卷人|I I 三、逻辑公式翻译(每小题6分，本题共12分11.将语句如果今天下雨，那么明天的比赛就要延期翻译成命题公式.12.将语句地球是圆的，太阳也是圆的翻译成命题公式.|得分|评卷人|I I 四、判断说明题判断各题正误，并说明理由.每小题7分，本题共14分13.设A=恼，b，c，d,R=,，则R是等价关系.14.(V x)(P(x)QCy)R(x)中量词V

4、的辖域为(P(x)Q(y).|得分|评卷人i|I I 五、计算题(每小题12分，本题共36分15.设集合A=怡，b，c，B=忡，c,d，试计算(1)A UB;100(2)A-B;(3)AXB.16.设G=，V=Vl,V2,V3,V4,E=(Vl,V2)(叫，V3),(Vl,V4),(V2,V3),(V3叫)，试(1)给出G的图形表示;(2)写出其邻接矩阵;(3)求出每个结点的度数;(4)画出其补图的图形.17.试利用Kruskal算法求出如下所示赋权图中的最小生成树(要求写出求解步骤L并求此最小生成树的权.V圄8 j得分|评卷人|I I 六、证明题本题共8分)18.试证明:PQ=P-，(P-，

5、Q).;I!l 101 试卷代号:1009国家开放大学(中央广播电视大学)2017年秋季学期开放本科期未考试离散数学(本)试题答案及评分标准(半开卷)(供参考)一、单项选择题每小题3分，本题共15分l.B 2.D 3.C 二、填空题(每小题3分，本题共15分)6.1,2,3 7.,8.15 9.m 10.假(或F，或0)三、逻辑公式翻译(每小题6分，本题共12分)11.设p.今天下雨，Q:明天的比赛就要延期.则命题公式为:PQ.12.设p:地球是圆的，Q:太阳是圆的.则命题公式为:PQ.四、判断说明题(每小题7分，本题共14分13.错误-4.D R不是等价关系，因R中不含，故不满足自反性-14

6、.正确.辖域为紧接量词V之后的最小子公式(P(X)八Q(y).五、计算题(每小题12分，本题共36分)15.(1)AUB=a,b,c,d;(2)A-B=a;5.A 2018年1月(2分)(6分(2分(6分)(3分)(7分)(3分)(7分)(4分)(8分)(3)AXB=，,102(1 2分)16.(1)G的图形表示如图一所示zV3 v4 图一(3分)(2)邻接矩阵:o 1 1 1 101 0 1 101 101 0(6分(3)deg(vj)=3,deg(vz)=2,deg(V3)=3,deg(V4)=2(9分)(4)补图如图二所示:Vj o V3 V4 图二(12分)17.用Kruskal算法求

7、产生的最小生成树.步骤为:切(Vj，v7)=1选ej=VjV7 W(V7，v4)=1选ez=V7叫W(Vj，叫)=2选e3=VjV6 W(V3，叫)=3选e4=V3叭103 W(Vz，听)=4选es=V2V1 W(V5，V1)=5选e6=VSV1 最小生成树如图三所示:V画图三最小生成树的权W(T)=l十1+2+3+4十5=16.说明z用其他方法，结果正确参照给分.六、证明题(本题共8分18.证明:(1)PQ(2)P P P(附加前提)(6分(9分)(1 2分)(1分(2分)(3)Q T(1)(2)1(4分)(4)P八QT(2)(3)1(5分)(5)-(,PV-Q)T(的E(6分(6)-.(P-.Q)T(5)E(7分)(7)P-.(P-.Q)CP规则(8分)说明:因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分.另，可以用真值表验证.104