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

1、離散數(shù)學期末試題一、單項選擇題（每小題3分，本題共15分）1若集合A=1，1，2，1，2，則下列表述正確的是( ) A2A B1，2AC1A D2 A正確答案：A2集合A=x|x為小于10的自然數(shù)，集合A上的關系R=|x+y=10且x, y A，則R的性質(zhì)為（ ） A自反的 B對稱的C傳遞且對稱的 D反自反且傳遞的正確答案：B3n階無向完全圖Kn的邊數(shù)及每個結(jié)點的度數(shù)分別是（ ） An(n-1)/2，n-1 Bn-1，n Cn(n-1), n-1 Dn(n-1), n正確答案：A4若完全圖G中有n個結(jié)點(n2)，m條邊，則當（ ）時，圖G中存在歐拉回路An為奇數(shù) Bn為偶數(shù) Cm為奇數(shù) Dm為

2、偶數(shù)正確答案：Aooooooabcdef3圖G如圖一所示，以下說法正確的是( ) A(a，b)是邊割集 B a，c是點割集 Cd是點割集 D (c，d)是邊割集正確答案：C5已知圖G的鄰接矩陣為 則G有（ ） A6點，8邊 B6點，6邊 C5點，8邊 D5點，6邊正確答案：D5下列公式成立的為( )APQ PQ BPQ PQ CP P DP(PQ) Q正確答案：C二、填空題（每小題3分，本題共15分）6設集合Aa，那么集合A的冪集是 正確答案：,a7如果R是非空集合A上的等價關系，a A，bA，R，則可推知R中至少包含 等元素正確答案：，8若A=1,2，R=|xA, yA, x+y4，則R的自

3、反閉包為 正確答案：,8設G是有20個結(jié)點，25條邊的連通圖，則從G中刪去 條邊，可以確定圖G的一棵生成樹正確答案：69設連通平面圖G的結(jié)點數(shù)為5，邊數(shù)為6，則面數(shù)為 正確答案：310設個體域D1,2，則謂詞公式消去量詞后的等值式為 正確答案：A(1) A(2)10(x)(P(x)R(y)S(z) 中的約束變元有 正確答案：x三、邏輯公式翻譯（每小題6分，本題共12分）11將語句“他們?nèi)ヂ糜危瑑H當明天天晴”翻譯成命題公式正確答案：設P：他們?nèi)ヂ糜危琎：明天天晴. PQ：他們?nèi)ヂ糜?，僅當明天天晴12將語句“如果明天下雨，則我們就在室內(nèi)上體育課”翻譯成命題公式正確答案：設 P：明天下雨， Q：我們

4、在室內(nèi)上體育課. 則命題公式為：P Q四、判斷說明題（每小題7分，本題共14分）13設集合A=1，2，B=3，4，從A到B的關系為f=，則f是A到B的函數(shù)正確答案：錯誤 ooooabcd圖一因為A中元素1有B中兩個不同的元素與之對應，故f不是A到B的函數(shù)13若偏序集的哈斯圖如圖一所示， 則集合A的最大元為a，極小元不存在正確答案：錯誤.b,c,d都是極小元.五、計算題（每小題12分，本題共36分）15設集合A=a, b, c，B=a, c，試計算（1）（AB）； （2）（B - A）； （3）（AB）B正確答案：（1）（AB）=c； （2）（B - A）=a； （3）（AB）B=, 16設G=

5、，V=v1, v2, v3, v4, v5，E=(v1,v3) , (v1,v5) , (v2,v3) , (v2,v5) , (v3,v4)，試（1）給出G的圖形表示； （2）寫出其鄰接矩陣；（3）求出每個結(jié)點的度數(shù)； （4）畫出其補圖的圖形oooov1v2v3v4圖二v5o正確答案：（1）（2）oooov1v2v3v4圖三v5o（3）v1，v2，v3，v4，v5結(jié)點的度數(shù)依次為2，2，3，1，2（4）17求（PQ）（RQ）的析取范式，合取范式正確答案：（PQ）（RQ） （PQ）（RQ） （4分） (PQ)（RQ） (PRQ)(QRQ)(PRQ)17試畫一棵帶權(quán)為2, 3, 3, 4, 5,的最優(yōu)二叉樹,并計算該最優(yōu)二叉樹的權(quán)ooooooooo23345510717正確答案：最優(yōu)二叉樹如圖所示權(quán)為23+33+32+42+52=39六、證明題（本題共8分）18試證明集合等式A (BC)=(AB) (AC) 證明：設S= A (BC)，T=(AB) (AC)，若xS，則xA或xBC，即 xA或xB 且 xA或xC 也即xAB 且 xAC ， 即 xT，所以ST 反之，若xT，則xAB 且 xAC， 即xA或xB 且 xA或xC， 也即xA或xBC，即xS，所以TS 因