2014年離散數(shù)學(xué)期末試題1009

1、離散數(shù)學(xué)期末試題一、單項選擇題(每小題3分,本題共15分)1.若集合A=1,，2,1,2，則下列表述正確的是().A.2gAB.1,2uAC.1AD.2uA正確答案：A2集合A=x|x為小于10的自然數(shù),集合A上的關(guān)系R=|x+y=10且x,y,則R的性質(zhì)為().B.對稱的A.自反的C.傳遞且對稱的D.反自反且傳遞的正確答案：B).3.n階無向完全圖Kn的邊數(shù)及每個結(jié)點的度數(shù)分別是A.n(n-1)/2,n-1B.n-1,nC.n(n-1),n-1D.n(n-1),n正確答案：A時，圖G中存在歐拉回路D.m為偶數(shù)4.若完全圖G中有n個結(jié)點(n三2),m條邊，則當(dāng)(A.n為奇數(shù)B.n為偶數(shù)C.m為

2、奇數(shù)正確答案：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分)設(shè)集合A=a，那么集合A的幕集是.正確答案：0,a如果R是非空集合A上的等價關(guān)系，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設(shè)G=V,E是有20個結(jié)點，25條邊的連通圖，則從G中刪去條邊,可以確定圖G的一棵生成樹.正確答案：6設(shè)連通平面圖G的結(jié)點數(shù)為5,邊數(shù)為6,則面數(shù)為.正確答案：3設(shè)個體域D=1,2,則謂詞公式VxA(x)消去量詞后的等值式為.正確答案：A(1)aA(2)(Vx)(P(x)TR(y)VS(z)中的約束變元有.正確答案：x三、邏輯公式翻譯(每小題6分，本題共12分)將語句“他們?nèi)ヂ糜?，僅當(dāng)明天天晴.”翻譯成命題公式.正確答案：設(shè)P：他們?nèi)ヂ糜?，Q：明天天晴.PTQ:他們?nèi)ヂ糜危瑑H當(dāng)明天天晴.將語句“如果明天下雨，則我們

4、就在室內(nèi)上體育課.”翻譯成命題公式.正確答案：設(shè)P：明天下雨，Q：我們在室內(nèi)上體育課.則命題公式為：PtQ.四、判斷說明題(每小題7分，本題共14分)設(shè)集合A=1,2,B=3,4,從A到B的關(guān)系為/=,，則f是A到B的函數(shù).正確答案：錯誤.因為A中元素1有B中兩個不同的元素與之對應(yīng)，故f不是A到B的函數(shù).d若偏序集A,R的哈斯圖如圖一所示，則集合A的最大元為a,極小元不存在.正確答案：錯誤.b,c,d都是極小元.五、計算題(每小題12分，本題共36分)15.設(shè)集合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設(shè)G=,V=%v2,v3,v4,v5,E=(v1,v3),%匕),(v2,v3),(v2,v5),(v3,v4)，試(1)給出G的圖形表示；(2)寫出其鄰接矩陣；(3)求出每個結(jié)點的度數(shù)；(4)畫出其補(bǔ)圖的圖形.正確答案(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試畫一棵帶權(quán)為2,3,3,4,5,的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權(quán)正確答案：最優(yōu)二叉樹如圖所示23權(quán)為2x3+3x3+3x2+4x2+5x2=39六、證明題(本題共8分)試證明集合等式Au(BC)=(AB)c(AuC).證明：設(shè)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