2014年离散数学期末试题1009

1、离散数学期末试题一、单项选择题(每小题3分,本题共15分)1.若集合A=1,，2,1,2，则下列表述正确的是().A.2gAB.1,2uAC.1AD.2uA正确答案：A2集合A=x|x为小于10的自然数,集合A上的关系R=|x+y=10且x,y,则R的性质为().B.对称的A.自反的C.传递且对称的D.反自反且传递的正确答案：B).3.n阶无向完全图Kn的边数及每个结点的度数分别是A.n(n-1)/2,n-1B.n-1,nC.n(n-1),n-1D.n(n-1),n正确答案：A时，图G中存在欧拉回路D.m为偶数4.若完全图G中有n个结点(n三2),m条边，则当(A.n为奇数B.n为偶数C.m为

2、奇数正确答案：A3.ABCD.图G如图一所示,以下说法正确的是(a,b)是边割集a,c是点割集9是点割集(c,)是边割集).aoc一0oe正确答案：C5.已知图G的邻接矩阵为).8边8边则G有(A.6点C.5点正确答案：D5.下列公式成立的为(A.PAQoVQC.PnPB.6点，D.5点，6边6边).B.oPQD.PA(PVQ=Q正确答案：C欢迎下载 二、填空题(每小题3分，本题共15分)设集合A=a，那么集合A的幕集是.正确答案：0,a如果R是非空集合A上的等价关系，aeA,beA,a,beR,则可推知R中至少包含等元素.正确答案：a,a，b,b，a,b，b,a若A=1,2,R=x,y|xe

3、A,yeA,x+y4，则R的自反闭包为.正确答案：1,1,2,2,1,2,2,1设G=V,E是有20个结点，25条边的连通图，则从G中删去条边,可以确定图G的一棵生成树.正确答案：6设连通平面图G的结点数为5,边数为6,则面数为.正确答案：3设个体域D=1,2,则谓词公式VxA(x)消去量词后的等值式为.正确答案：A(1)aA(2)(Vx)(P(x)TR(y)VS(z)中的约束变元有.正确答案：x三、逻辑公式翻译(每小题6分，本题共12分)将语句“他们去旅游，仅当明天天晴.”翻译成命题公式.正确答案：设P：他们去旅游，Q：明天天晴.PTQ:他们去旅游，仅当明天天晴.将语句“如果明天下雨，则我们

4、就在室内上体育课.”翻译成命题公式.正确答案：设P：明天下雨，Q：我们在室内上体育课.则命题公式为：PtQ.四、判断说明题(每小题7分，本题共14分)设集合A=1,2,B=3,4,从A到B的关系为/=,，则f是A到B的函数.正确答案：错误.因为A中元素1有B中两个不同的元素与之对应，故f不是A到B的函数.d若偏序集A,R的哈斯图如图一所示，则集合A的最大元为a,极小元不存在.正确答案：错误.b,c,d都是极小元.五、计算题(每小题12分，本题共36分)15.设集合A=a,b,c,B=a,c,试计算(1)(AAB)；(2)(B-A)；(3)(AAB)XB.正确答案：(1)(AAB)=c；(2)(

5、B-A)=a(3)(AAB)xB=,16设G=,V=%v2,v3,v4,v5,E=(v1,v3),%匕),(v2,v3),(v2,v5),(v3,v4)，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形.正确答案(1)图v50010100101(2)110100010011000v1，v2，v34)图三2，3，1，2.求(PVQ)f(RVQ)的析取范式，合取范式.正确答案：(PVQ)f(RVQ)4分)(PVQ)V(RVQ)o(PAQ)V(RVQ)RPQ)A(QVRVQ)(PVRVQ)17试画一棵带权为2,3,3,4,5,的最优二叉树,并计算该最优二叉树的权正确答案：最优二叉树如图所示23权为2x3+3x3+3x2+4x2+5x2=39六、证明题(本题共8分)试证明集合等式Au(BC)=(AB)c(AuC).证明：设S=Au(BcC),T=(AuB)c(AuC),若xS,则xA或xBcC,即xA或xB且xA或xWC.也即xAuB且xAuC,即xWT,所以SuT.反之，若xT,贝9xGAuB且xAuC,即xGA或xGB且xGA或xGC,也即xGA或xWBcC,即xGS,所以TuS.因此T=S