国开离散数学2015年3月份试题

1、 离散数学(本)2015年3月份试题一、单项选择题(每小题3分，本题共15分)设A=1,3,5,7,9,B=2,4,6,A到B的关系R=vx,ylx=y+1,则R=().A,B,C.,D.,若集合A=a,b,c,则下列表述正确的是().A.0gAB.aeAC.a,b,ceAD.acA设个体域为整数集，则公式Vx3y(x+y=10)的解释可为().对任一整数x存在整数y满足x+y=10存在一整数x有整数y满足x+y=10存在一整数x对任意整数y满足x+y=10任一整数x对任意整数y满足x+y=10设G为连通无向图,则()时,G中存在欧拉回路.A.G存在两个奇数度数的结点B.G不存在奇数度数的结点

2、C.G存在一个奇数度数的结点D.G存在偶数度数的结点n阶无向完全图K的边数及每个结点的度数分别是().nAn(n-1),nBn-1,nCn(n-1)/2,n-1Dn(n-1),n-1二、填空题(每小题3分,本题共15分)TOC o 1-5 h z设集合A=1,2,B=2,3,C=3,4,则AUB-C=.设A=a,b,B=1,2,C=a,b，从A到B的函数f=,，从B到C的函数g=,则gf等于.设G=是一个图，则G的结点度数之和为.设G是具有n个结点m条边k个面的连通平面图，则n+k-2=.设个体域D=1,2,3,A(x)为“小于1”,则谓词公式(Vx)A(x)的真值为.三、逻辑公式翻译(每小题

3、6分,本题共12分)将语句“如果明天下雨,则明天活动取消”翻译成命题公式.将语句“A是大写字母，B是小写字母.”翻译成命题公式.四、判断说明题(判断各题正误,并说明理由每小题7分,本题共14分)设A=a,b,c,R=,则R是等价关系.(Vx)(P(x)AQ(y)fR(x)中量词V的辖域为(P(x)AQ(y)fR(x).五计算题(每小题12分,本题共36分).设集合A=a,b,c,B=a,b,试计算(1)Ab；(2)A-B；(3)AXB.设G=,V=v1,v2,v3,v4,E=(v1,v3),(v2,v3),(v3,v4),试（1）给出G的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数

4、；（4）画出其补图的图形17.试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权v3六、证明题（本题共8分）18.试证明：q（PAqQ）AqR人（QtR）=qP.9分) 离散数学（本）2015年3月份试题参考解答一、单项选择题（每小题3分，本题共15分）1A2D3A4B5C二、填空题（每小题3分，本题共15分）61,27,8.边数的两倍（或：2IEI）9m10.假（或F,或0）三、逻辑公式翻译（每小题6分，本题共12分）TOC o 1-5 h z设P：明天下雨，Q：明天活动取消.（2分）则命题公式为：PtQ.（6分）设P：A是大写字母，Q：B是小

5、写字母.（2分）则命题公式为：PAQ.（6分）四、判断说明题（每小题7分，本题共14分）错误.（3分）R不是等价关系，因R中不包含，故不满足对称性.（7分）错误.（3分）辖域为紧接量词V之后的最小子公式（P（x）AQ（y）.（7分）计算题（每小题12分，本题共36分） HYPERLINK l bookmark8 （1）AUB=a,b,c,a；（4分）（2）A-B=a,c；（8分）(3)AXB=Va,a,16.（1）G的图形表示如图一所示:2)v4(12分)(3分)6分)3)deg(v1)=1，deg(v2)=1deg(v3)=3deg(v4)=1 4）补图如图二所示：v图v2v3v412分）17用Kruskal算法求产生的最小生成树步骤为：w(v2,v6)=1，选(v2,v6)w(v4,v5)=1,选(v4,v5)W(V,V6)=2,选(V,v6)w(v3,v4)=3,选(v3,v4)w(v2,v3)=4,选(v2,v3)最小生成树如图三所示6分）v39分）12分）最小生成树的权C（T）=1+1+2+3+4=11六、证明题（本题共8分）18证明：（1）i（PAqQ）P(1分)(2)qPVQT(1)E(3分)(3)(QtR)P(4分)(4)iRP(5分)（5）iQT(3)(4)I(6分)6