最新國(guó)家開(kāi)放大學(xué)電大【離散數(shù)學(xué)(本)】期末題庫(kù)及答案考試說(shuō)明：本人針對(duì)該科精心匯總了歷年題庫(kù)及答案，形成一個(gè)完整的題庫(kù)，并旦每年都在更新。該題庫(kù) 對(duì)考生的復(fù)習(xí)、作業(yè)和考試起著非常重要的作用，會(huì)給您節(jié)省大量的時(shí)間。做考題時(shí)，利用本文檔中的查 找工具，把考題中的關(guān)鍵字輸?shù)讲檎夜ぞ叩牟檎覂?nèi)容框內(nèi)，就可迅速查找到該題答案。本文庫(kù)還有其他網(wǎng) 核及教學(xué)考一體化答案，敬請(qǐng)查看?！倦x散數(shù)學(xué)】題庫(kù)及答案一一、單項(xiàng)選擇題(每題3分，此題共15分)1. 假設(shè)集合 A=a, b9 B= a, b, ( a, b ),則().A. AciB,且B. AeBf但力芯C. A(zB9 但 AwBD. 旦ZaB2. 集合Z=1, 2, 3, 4, 5, 6, 7, 8上的關(guān)系夫=5 y>|x+y=10且x, ,則&的性質(zhì)為().A.自反的B.對(duì)稱的C.傳遞旦對(duì)稱的D.反自反且傳遞的3. 如果R和人2是Z上的自反關(guān)系，則R1UR2, RQR2,中自反關(guān)系有()個(gè).A. 0B. 2C. 1D. 34. 如圖一所示，以下說(shuō)法正確的選項(xiàng)是()A.但,時(shí)是割邊B. («, e)是邊割集C. 時(shí)0,現(xiàn)是邊割集D. (<e)是邊割集圖一5. 設(shè)N (x)： x是人，B (x)： x是學(xué)生，則命題“不是所有人都是學(xué)生可符號(hào)化為().A. ( V x)(4(a) A5(x)B. (3x)(24(x)AB(x)C n (Vx)(?l(x) fg(x)D. - (3x)(x)A-| 5(x)二、填空題(每題3分，此題共15分)6. 假設(shè)集合力的元素個(gè)數(shù)為10,則其驀集的元素個(gè)數(shù)為.7. 設(shè)A=af b, c), B=1, 2,作/： 4-B,則不同的函數(shù)個(gè)數(shù)為.8. 假設(shè)力=12，R=<x.y>xA,yA,x+y=G,則R 的自反閉包為9. 結(jié)點(diǎn)數(shù)y與邊數(shù)e滿足關(guān)系的無(wú)向連通圖就是樹(shù).10. 設(shè)個(gè)體域D=a, b,c9則謂詞公式(VxM(x)消去量詞后的等值式為三、邏輯公式翻譯(每題6分，此題共12分)11. 將語(yǔ)句“盡管他接受了這個(gè)任務(wù)，但他沒(méi)有完成好翻譯成命題公式.12. 將語(yǔ)句“今天沒(méi)有下雨翻譯成命題公式.四、判斷說(shuō)明題(每題7分，木題共14分)判斷下面各題正誤，并說(shuō)明理由.13. 下面的推理是否正確，試予以說(shuō)明.(1) (Vx) F(X)-G (x)前提引入(2) F (y) -G (y)US (1).14. 假設(shè)偏序集<4,的哈斯圖如圖二所示，則集合的最大元為s最小元不存在.五. 計(jì)算題(每題12分，此題共36分)15. 求(PV。)一(RV。)的合取范式.16. 設(shè)刀=0, 1, 2, 3, 4), 7?=(<x, y>xA, yeA _H. x+y<0), S=<xf y>xeA, yeA x+y<3,試 求 R, S, R,S, R-i, L, r(R)17. 畫一棵帶權(quán)為1, 2, 2, 3, 4的最優(yōu)二叉樹(shù)，計(jì)算它們的權(quán).六、證明題(此題共8分)18. 設(shè)G是一個(gè)階無(wú)向簡(jiǎn)單圖，是大于等于2的奇數(shù).證明G與&中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等(° 是G的補(bǔ)圖).試題解答一、單項(xiàng)選擇題每題3分，此題共15分 1. A 2. B 3. B 4. D 5. C二、填空題(每題3分，此題共15分)6. 10247. 88. (<1,1>,<2,2>9. e=v10. A (a) /A (b)( u)三、邏輯公式翻譯每題6分，此題共12分 11. 設(shè)他接受了這個(gè)任務(wù)，Q：他完成好了這個(gè)任務(wù)，2分 PzQ6分 12. 設(shè)F：今天下雨，2分 -yP.6 分 四、判斷說(shuō)明題每題7分，此題共14分 13. 錯(cuò)誤.3分 2 應(yīng)為F -G x ,換名時(shí)，約束變?cè)c自由變?cè)荒芑煜?7分 14. 錯(cuò)誤.3分 集合A的最大元不存在，。是極大元.7分 五. 計(jì)算題每題12分，此題共36分 15. (PV2)一 (7?Vg)4分 12 分 2分 4分 6分 8分 10 分 12 分 (PV0) V (RV。)<(-nPA->e)V (RVQ)頃V& V o)/ (2 V R V。)=(2V&V。)AR 合取范式16. R=0, 5=<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0> &S=0,E=0,s'=s,RR)=L.權(quán)為 1x3+2x3+2x2+3x2+4x2=2710 分 12 分 六、證明題此題共8分 18.證明：因?yàn)?quot;是奇數(shù)，所以階完全圖每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，3分 因此，假設(shè)G中頂點(diǎn)y的度數(shù)為奇數(shù)，則在。中y的度數(shù)一定也是奇數(shù)， 6分 所以G與&中的奇數(shù)度頂點(diǎn)個(gè)數(shù)相等.8分 【離散數(shù)學(xué)】題庫(kù)及答案二一、單項(xiàng)選擇題每題3分，此題共15分 1.假設(shè)集合4=1,1, 2,則下面表述正確的選項(xiàng)是 .A.B. 1曲C.D. 2 eA2.已知一棵無(wú)向樹(shù)中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，的樹(shù)葉數(shù)為 .A.B. 4C. 3D- 53.設(shè)無(wú)向圖G的鄰接矩陣為0111110011100001100111010則G的邊數(shù)為)A. 1B. 7C. 6D. 144 .設(shè)集合A=a,則刀的驀集為)A. 。B。， aC.°，。D. (0, a5-下面公式中 為永真式.A.C.二、填空題每題3分，此題共15分 6. 命題公式尸a tP的真值是.7. 假設(shè)無(wú)向樹(shù)有5個(gè)結(jié)點(diǎn)，則的邊數(shù)為8. 設(shè)正則也叉樹(shù)的樹(shù)葉數(shù)為分支數(shù)為j,則"1 7 9. 設(shè)集合力=1, 2上的關(guān)系7? = <1,1>,<1,2>,則在&中僅需加一個(gè)元素,就可使新得到的關(guān)系為對(duì)稱的.10. Vx Ax Bxf z VCy 中的自由變?cè)? 三、邏輯公式翻譯每題6分，此題共12分 11. 將語(yǔ)句“今天上課.翻譯成命題公式.12. 將語(yǔ)句“他去操場(chǎng)鍛煉，僅當(dāng)他有時(shí)間.翻譯成命題公式.四、判斷說(shuō)明題每題7分，此題共14分 判斷下面各題正誤，并說(shuō)明理由.13. 設(shè)集合力=1, 2, B=3, 4 ,從刀到8的關(guān)系為1,3 ,貝是力到B的函數(shù).14. 設(shè)G是一個(gè)有4個(gè)結(jié)點(diǎn)10條邊的連通圖，則G為平而圖.五. 計(jì)算題每題12分，此題共36分 15. 試求出PV。 一RV。 的析取范式.16.設(shè)刀=1,1,2, 3=1, 2,試計(jì)算(2) C4UB)17. 圖 G=<V9 £>,其中 V= %b,c,d, E=心)，(。,c),(% d),(b,c),(b, d),(c,力,對(duì)應(yīng)邊的權(quán)值依 次為1、2、3、1、4及5,試1 畫出G的圖形;2 寫出G的鄰接矩陣;3 求出G權(quán)最小的生成樹(shù)及其權(quán)值.六、證明題此題共8分 18. 試證明：假設(shè)r與s是集合刀上的自反關(guān)系，貝U&ns也是集合力上的自反關(guān)系.試題解答一、單項(xiàng)選擇題每題3分，此題共15分 1- B 2. D 3. B 4. C 5. B二、填空題每題3分，此題共15分 6.假或F,或0 7.8.9.<2, 1>10.z, y三、邏輯公式翻譯每題6分，此題共12分 11.設(shè)今天上課,2分 6分 12.設(shè)F：他去操場(chǎng)鍛煉，Q：他有時(shí)間,2分 則命題公式為：P.4分 8分 12 分 4分 8分 12 分 6分 則命題公式為：PT0 四、判斷說(shuō)明題每題7分，木題共14分 13. 錯(cuò)誤.3分 因?yàn)榱χ性?沒(méi)有8中元素與之對(duì)應(yīng)，故/不是力到8的函數(shù).7分 14. 錯(cuò)誤.3分 不滿足“設(shè)G是一個(gè)有y個(gè)結(jié)點(diǎn)e條邊的連通簡(jiǎn)單平面圖，假設(shè)v3,則eW3/6.7分 五.計(jì)算題每題12分，此題共36分 15. (PV2)一(RV。)。-I (PV0V (RV。)= ("E 0V (RV。)=(1尸人1 g)v7?ve (析取范式)16. (1) UAB) =1(2) C4U3) =1,2, 1,2(3) A- (A QB) =(1, 1,217. (1) G的圖形表示如圖一所示：3分 6分 。1C圖二權(quán)為：1+1+3=5圖一2 鄰接矩陣：_o 1 1 r10 11110 11110MBMB3 最小的生成樹(shù)如圖二中的粗線所示:(10 分)(12 分)六、證明題此題共8分 18.證明：設(shè)VxgJ,因?yàn)?amp;自反，所以x Rx, BP<x,x>g7?；又因?yàn)镾自反，所以xRx,即<x,x>eS.即 Vx, x>eROS故ACS自反.4分 6分 8分 【離散數(shù)學(xué)】題庫(kù)及答案三一、單項(xiàng)選擇題每題3分，此題共15分 1.假設(shè)集合A = a, ,則下面表述正確的選項(xiàng)是 .A. /zo4C.D. 0gA2.命題公式PVQ 的合取范式是 A.(PA2)B. (PA0) V (PVg)C.D. i (P /Q)3.無(wú)向樹(shù)r有8個(gè)結(jié)點(diǎn),則T的邊數(shù)為 .A.Be 7C. 8D.A.C.5.A.C.4.圖G如圖一所示,以下說(shuō)法正確的選項(xiàng)是 .a是割點(diǎn)缶d是點(diǎn)割集圖一下面公式成立的為 .P/Q = P/QQPnPB. 0 c是點(diǎn)割集D. c是點(diǎn)割集B. P->-iQ = TtQD.PQ)n。二、填空題每題3分，此題共15分 6. 設(shè)集合4=2.3,4, B=1,2, 3,4, R是刀到8的二元關(guān)系,7? = (<x.y > xe Ay e<y則R的有序?qū)蠟?. 如果R是非空集合力上的等價(jià)關(guān)系，aeA,心,則可推知&中至少包含等元素.8. 設(shè)G=<V,E>是有4個(gè)結(jié)點(diǎn)，8條邊的無(wú)向連通圖，則從G中刪去條邊，可以確定圖G的一棵生成樹(shù).9. 設(shè)G是具有個(gè)結(jié)點(diǎn)m條邊上個(gè)面的連通平面圖，則m等于10. 設(shè)個(gè)體域。=1,2,刀為大于1，則謂詞公式(3x)Ax)的真值為三、邏輯公式翻譯(每題6分，木題共12分)11. 將語(yǔ)句“今天考試，明天放假翻譯成命題公式.12. 將語(yǔ)句“我去旅游，僅當(dāng)我有時(shí)間翻譯成命題公式.四、判斷說(shuō)明題(每題7分，此題共14分)判斷下面各題正誤，并說(shuō)明理由.13. 如果圖G是無(wú)向圖，且其結(jié)點(diǎn)度數(shù)均為偶數(shù)，則圖G是歐拉圖.14. 假設(shè)偏序集V4,人>的哈斯圖如圖二所示，則集合Z的最大元為最小元是八五. 計(jì)算題(每題12分，此題共36分)15 .設(shè)謂詞公式(女)(刀(x, y) T (Vz)5(y, x, z),試(1) 寫出量詞的轄域；(2)指出該公式的自由變?cè)图s束變?cè)?16. 設(shè)集合 /=,1,2, 8=1,1,2,試計(jì)算(1) C48) ；(2) C4C1B) ；(3) AXB.17. 設(shè) G=<V, E>, V=v, v2> 巧，v4 ), E=(vi,V3), (v2,v3), (v2,v4)，(巧皿)，試(1)給出G的圖形表示； (2)寫出其鄰接矩陣；(3) 求出每個(gè)結(jié)點(diǎn)的度數(shù)；(4)畫出其補(bǔ)圖的圖形.六、證明題(此題共8分)18. 設(shè)力，B是任意集合，試證明：假設(shè)Ax4=BxB,則試題解答供參考 一、單項(xiàng)選擇題每題3分，此題共15分 1. A 2. C 3. B 4. B 5 D二、填空題每題3分，此題共15分 6. <2, 2>, <2, 3>, <2,4>, <3, 3> , <3, 4>, <4, 4> 7. <a, a >, < b, b>8. 59 . n+k-210. 真或T,或1 三、邏輯公式翻譯每題4分，此題共12分 11. 設(shè)P：今天考試，Q：明天放假.2分 則命題公式為：PA06分 12. 設(shè)F：我去旅游，Q：我有時(shí)間，2分 則命題公式為：PT06分 四、判斷說(shuō)明題每題7分，木題共14分 13. 錯(cuò)誤.3分 當(dāng)圖G不連通時(shí)圖G不為歐拉圖.7分 14. 錯(cuò)誤.3分 集合力的最大元與最小元不存在，a是極大元，/是極小元，7分 五. 計(jì)算題每題12分，此題共36分 15. 1 女量詞的轄域?yàn)橐詘,v TVz 33,x,z ,3 分 Vz量詞的轄域?yàn)閤, z ,6分 2 自由變?cè)獮橐詘,v tVz 33,x,z 中的，9分 約束變?cè)獮閤與z12分 16. 1 Z3=1,24 分 2 ACIB=18 分 (3) Q8=v1,1>, <1,1,2>,<1, 1,2>, <2,1>, <2,17. (1) G的圖形表示為(如圖三)：3分 3 n，v2,巧，四結(jié)點(diǎn)的度數(shù)依次為1，2, 3, 24 補(bǔ)圖如圖四所示：6分 9分 12 分 1分 3分 5分 6分 7分 8分 六、證明題此題共8分 18. 證明：設(shè) xeAf 則Vv, x>eAxA,因?yàn)?AxA=BxB,故x>gBxB9 則有 所以AB.設(shè)則Vx, x>gBxB,因?yàn)?4xA=BxB,故Vx, x>eAxA,則有 xeA,所以 故得A=B.【離散數(shù)學(xué)】題庫(kù)及答案四一、單項(xiàng)選擇題每題3分，此題共15分 1. 設(shè) A=(1，3.5,7,9).R=(2，6),A 到 H 的關(guān)系 R-，：Vz .】>! r-y-1) .則 R=(>.A. (<U2>,<2.3>.<3.4>>H(Vl.2>,V3.4>V5.6>G <1.1>,<2,2>.<3.6>).(V3.2>V54>,V?6>)2. 假設(shè)餐合A =.則下面表芯正確的選項(xiàng)是().A. (ciEMcOWAC. (u,b6AD.0eA3. 段個(gè)體it為集合(1.2.34.5 .則公式(V)【3少(工+】=5)的解釋可為().A.存在一整數(shù)g有整數(shù)y滴足x+>=5a對(duì)任一整數(shù)工存在整數(shù)y滴足*+】=5C. 存在一整數(shù)4對(duì)任恿整數(shù)y滿足工+】=5D. 任一整數(shù)工對(duì)任意整致y清足x+y=54. 沒(méi)仁為連通無(wú)向圖.蝸(時(shí),a中存在歐拉回用.A.G存在兩個(gè)tSfttJM數(shù)的結(jié)點(diǎn)B.G存在一個(gè)奇數(shù)度數(shù)的常點(diǎn)GG不存在奇數(shù)度數(shù)的結(jié)點(diǎn)D.G存。偶數(shù)度數(shù)的結(jié)點(diǎn)乩n階無(wú)向完全圖K.的邊數(shù)及每個(gè)結(jié)點(diǎn)的度敬分別是().A"(n 1)與九11 ji(w-*1)/2與 一1C w 1 與 nD. n(n 1)與 « I二、填空題(每題3分，此題共15分)6. 設(shè)堡 & 1一1.2.3) =,：2.3).(/=口.4,刪.41)(3一()=7. 設(shè)Af 08F.2L" 從，利8的畫數(shù)/ =7V1>VO.2>.從B到C的函數(shù)拜=(<1.6><2心>).荊曠/等于.8. 設(shè)G = VVE>職一個(gè)圖.|E| = M.則“的捎點(diǎn)度敝之和為9. 設(shè)G是代有花邊&個(gè)而的連通平面圖.則刀+*-2=1D，設(shè)中怵城本=1.？.3.1J)為的2倍大于站.刖周刊公式IV那.4(/)的底值為三、邏輯公式翻譯(每題6分，此題共12分)11. 將語(yǔ)句“如果他掌握了計(jì)算機(jī)的用法，那么他就能完成這項(xiàng)工作翻譯成命題公式.12. 將語(yǔ)句“前天下雨，昨天還是下雨翻譯成命題公式.四、判斷說(shuō)明題(判斷各題正誤，并說(shuō)明理由.每題7分，此題共14分)13. 段.1 = % , A. c ) R ( V。， > < A . /，A V r V 以，6 > V 內(nèi), > , V 右，4 A VrM> 姻R是等價(jià)關(guān)系.14. ( Vx)CP< r)AQ【y)f Rtr>)中世詞 丫 的轄帔為(P。)AQ( y)L五、計(jì)算題(每題12分，此題共36分)15. 設(shè)陞臺(tái)八=d)Hr站日)，試算(1)4 UBi (2)A/h (3)AXB.'StV， E >,V* = < HT»,口,.£ = 叫."c 玖,饑 .叫.口、 .【化. 5 >, s 試l>紛出G的圖形&示，12>耳出其鄰也如所，【3 求出每個(gè)靖點(diǎn)的度【，>踴出北補(bǔ)圖的圖形.I 7.試?yán)肒ruskn W 未出如卜所況M技圖中的/»小生成俐要求寫出求解3項(xiàng)，.井 未此條小生成列的枳.試題答案一單項(xiàng)選擇BH每題3分,本18共恃分 1.02.A3.B4.C5.H二. 填空】!每小超3分.本弛共15分 6. 1.2.3 7. <<i.6>.<d.a> «. 2?；颍?|E| 9m10. 假或F.或。 三. 謠輻公式翩澤每小聘6分.本息共12分 IL i» PJlfctW了計(jì)算機(jī)的用法,Q：他推完成這項(xiàng)工作-2分 刪命題公式為，PfQ6分 12. 設(shè)P,前天下雨.Q沖天還是下闌.2分 則命88公式為：PAQ.；6分 四、判斷說(shuō)明網(wǎng)督小18 7分,本18共M分 13. 部誤.3分 R不是等價(jià)關(guān)系.因R中包含<a.b><ba>，但不包含V<2/>故不滿足傳遞性：1 分 14. 銷誤“心分 暗域?yàn)榫o惟St詞V之后的梭小子公式Px AQC.y -Rx .【7分 五計(jì)算1!每小12分,本11共36分 15. n AUB =a0cd i4 分2A 8 = c </ I(3) 4 XB(<a .a>.<a.b>.<b.u>,<b.b>.<c.u>.<c 5> Vd g > Vd E>)J6.i g的圖形&示ftn圖一所示,3分 (2郊接矩陣，0 1 1 110 10110 110 10【6分 (3)deg(vi )3, drg(-v：J - 2» dvg(Vi)&3.9分 degE ) = 2(4補(bǔ)圖如圖二所示,o12 分 17. 用Kruskal »法求產(chǎn)生的最小生成樹(shù).步驟為,w(vi »v:»3i J =i/ir6分 w( v> v? 4 選 ft =山巧 w【m.m)r9,選 = w【ms>=l8 .遺 w33=22.ii e.=y最小生小樹(shù)州圖三所示,圖三9分 戒樹(shù)的杖 m = 1 十3 +94 18+22=57六.證明題本J®共X分 (!) P VQ<1分 尸(3)Qptvnin 前撾T(D(2>r以分-3(r/P AQTf2)(3)/T(l)E(0)f( Pf 二 Q>T(5>ECP電則5分 6分 7分 8分 <7 PIftlUhiailE刪過(guò)慢中.公式引用的次序訶以不同般引用的提正瓊特1分.利川倆個(gè)公K 團(tuán)出有效結(jié)伯格1成2分,眼后同出站論得2或1分另.可以用頁(yè)值表臉證.【離散數(shù)學(xué)】題庫(kù)及答案五單項(xiàng)選擇題每題3分，此題共15分 1. 設(shè) A = 1.2,3,，8= (2,3,4,A 到 B 的關(guān)系 R - <x .>> I z 6 A G B .且.r + y= 5.tt!R = ().A. <<2>.V13>,V23>)EL <1.4>.<2.3>.<3»2>>(：.(V1.1>,V2.2>,V3,2>)D. (<3.2>,<2,4>.<3,4>>2. 假設(shè)集合A = M6,r.d).則下面表述正的的是<.A.06AC«M.d£AD. U.6JGA3 .設(shè)個(gè)體域?yàn)檎麛?shù)韭.燃公式(Vx)(3y)(x->=2>的解釋可為().A. 存在一整數(shù)工有整數(shù)y滿足x-y-2B. 存在一建數(shù)工對(duì)任意整數(shù)y滿足工一y = 2C. 對(duì)任一整數(shù)工存在整數(shù)】滴足x-y-2D. 任一整數(shù)1對(duì)任意整數(shù)滿足x-> = 24. "階無(wú)向完全圖K,的邊數(shù)及每個(gè)結(jié)點(diǎn)的度數(shù)分別是().A. n(w 與B. n( w 1)與 一1Cn 】與D. w(n 1)/2 與 rr 15. 設(shè)G為連通無(wú)向圖.則(時(shí)弓中存在歐拉回路.A.G不存在奇數(shù)度數(shù)的結(jié)點(diǎn)B.G存在一個(gè)新數(shù)度數(shù)的結(jié)點(diǎn)C.G存在兩個(gè)奇數(shù)度數(shù)的結(jié)點(diǎn)D.G存在偶數(shù)度數(shù)的結(jié)點(diǎn)評(píng)卷人二、填空題每小18 3分,本a共15分 6. 設(shè)集含工是小于4的正整數(shù) 用集合的列舉法.7. 設(shè) A = l,2 ,T2 ,CTl,2.從 A 到 B 的函數(shù)/ = Vlu>,V2,Q>.從 B到C的函致g = <a2>,V6.l>.則復(fù)合函數(shù).8. 設(shè)G-<V.E>是一個(gè)圖，結(jié)或度敬之和為30.則G的邊數(shù)為9. 設(shè)G是具有，個(gè)結(jié)點(diǎn)桁條邊個(gè)面的連通平面圖，姻+A-2=.10. 設(shè)個(gè)體域D = 2,3.4>.Ai 為七小于3，則謂同公式VjHAG 的真值為得分評(píng)卷人三!！福公式小IS 6分，本原共12分 11. 將語(yǔ)句“如果今天下雨.那么明天的比賽就要延期.疆譯成命題公式.得分評(píng)卷人12. 將語(yǔ)句“地球是倒的，太陽(yáng)也是圓的.翻譯成命題公式.四、判斷說(shuō)明IH判斷各題正誤，井說(shuō)明理由每小H 7分，此題共14分 13. 設(shè) Aa.b.c.d .R<a.h>9<b,a>,<a.a>9<b.b>.<c>,則 R 是等 價(jià)關(guān)系.14. ( Vx)(P(x)AQ(y)-R(x)中量詞 V 的轄域?yàn)?P(x> AQ(>).得分評(píng)卷入五計(jì)算每小MS 12分.本通共36分 15. 設(shè)集合A = k/>c).B = (3c,次).試計(jì)算 (l)A(JHi(3)AXB.16. 設(shè) G VVE> V (V| t vt ) E = (V| ) < (vj t (vi. v<) > (1/1 ti»i )(l>給出G的圖形衰示8(2)寫出其鄰接矩陣I(3)戒出每個(gè)站點(diǎn)的度數(shù),(4)®出其補(bǔ)圖的圖形.17. 試?yán)肒ru9kd算法求出如下所示賦權(quán)圖中的1ft小生或樹(shù)(妻求寫出求薪步轅，并 求此最小生成樹(shù)的權(quán).得分評(píng)卷人六、證明18(此題共8分)18.成征明r P-Q .試題及答案-項(xiàng)iswHim小m3分,本ai共is分 I. B2.D3.C4. D&A二, 堵空J(rèn)B每小HI 3分.本恥共15分 6. I.2.3 7. <<1.2>.<2.1»9. m10. fl<AF.«0>三、il輯公式小H6分.本HI共12分 H.今天下Ifl.QZI天的比賽就要14期.2分 副命MS公式為【6分 12.仗卜地球屈圓的，。太陽(yáng)是圓的.【2分 WlifrM公式為lPQ.6 分四、判斷說(shuō)明18每小JW 7分,本JB共14分 IX WiM.3 分 R不是等價(jià)關(guān)系.因R中不含VM>.故不fMMfl反性.7分 M.正確.“分 之后的 Jft 小子公 XPJc AQy> .7 分 五小H技分.本H共36分 15. AU8M.y</i4 分 2M-B-ah8 分 3 A XB <u.6 >.<a .>,<« I>9<b.b>.<b.c>.<b.d>t<r.b>.<c.12 分 16. (1 )G的圖形表如圖一所不:(2鄰接矩陣,ViWW4圖一(3分)d i i r10 10110 110 10 _(6分(3)<ieg(vi)= 3. dc&3$= 2, deg(0)= 3 deg(s> = 2(4補(bǔ)09如圖二所示i【9分)圖二曰2分)17. 用Kruskal W法求產(chǎn)生的最小生成樹(shù)步曩為：W(V| .vr) = lW(Vr ) = 1w(vj fVS) = 2w(v> =3選宜=ss 選 C：VfV. 選 ei = Viv< 選 c4 W(Vt VF ) = 4 選 Cs =VjV? w (Vj f Vt > = 5 ij ci 33 v$v? 最小生成鈣如圖三所示.【6分 圖三9分 最小生成樹(shù)的權(quán)W(T) = 1 + 1 + 2 + 3 + 4 + 5=16.12 分 說(shuō)明，用其他方法.結(jié)果正確參照給分.六證明18本境共8分 18.證明：(l)P-Q1分 (3)Q(4)PAQ(5UP V 9(6UQ)P附加前提 T(2)(3)/T(4)ET(5>E2分 4分 【5分 6分7分 (7Pr(rQ8分 說(shuō)明：因BE明過(guò)程中,公式引用的次序可以不同一般引用前提正確得1分,利用兩個(gè)公式 得出有效結(jié)論得1或2分，景后得出結(jié)論得2或1分.另可以用真值表驗(yàn)證.【離散數(shù)學(xué)】題庫(kù)及答案六一、單項(xiàng)選擇題每題3分，此題共15分 假設(shè)集臺(tái)人=(1.2.3.U .則下面我還不正確的M(A2.3)£AB. A 1.2,3.1)C, (1.23,4)W人D. leA2. 假設(shè)無(wú)向圖。的結(jié)點(diǎn)度數(shù)之和為20,則r；的邊數(shù)為( >A. 10a 20C.30D.5X無(wú)向圖G是根樹(shù)，結(jié)成數(shù)為1【)的(；的邊數(shù)為(>A.SR. 10Q9DJI4. ft A()：j是人(了)口是學(xué)生,刪母甌“村的人是學(xué)生可荷門化為(A. r ( v«t)(惑_r)f)B. ( 3)(A(x) AB(x)C (Yx)(A(x) AB(x)I), r <A r HJ > 】5. 下面的推理正唏的是().A* < 1H V x)F(x)-7(x)前提引人<2)F(>)-*G(y)US (1>.&【1)( 3 -r)F( J )-*G (x )前提引入(2)F(y)G(y)US().C. (1)( 3)(F( f >-*G(±>)的提引人FJM。()ES(1).D. (1)( 3JXF(x)-*Glr)前捉引人(2)F(ylt；【y)ES(D.二、填空題(每題3分，此題共15分)6. 設(shè)A = “.2.Bu 1.2.3 則A到B上不同的函散個(gè)散為7. fin個(gè)靖點(diǎn)的無(wú)向完全圖的邊數(shù)為%假設(shè)無(wú)向圖G中存在歐枚路但不存在歐拉回路，則6的布散度敬的結(jié)點(diǎn)有 9. 設(shè)(；是a 10個(gè)結(jié)點(diǎn)的無(wú)向連通圖.結(jié)點(diǎn)的度教之和為3。，則從G中JH去 條邊后使之變成樹(shù)-10. 設(shè)個(gè)體域D = < 1.2.3.1).則明詞公式(如 >人M )酒去旬俱后的等值式為三、邏輯公式翻譯(每題6分，此題共12分)11. 將語(yǔ)句“昨天下雨翻譯成命題公式.12. 將語(yǔ)句“小王今天上午或者去看電影或者去打球翻譯成命題公式.四、判斷說(shuō)明題判斷各題正誤，并說(shuō)明理由.每題7分，木題共14分 IX存在果合A與使得與同時(shí)成立.14, 完全圖K,是平面圖.五、計(jì)算題每題12分，此題共36分 15. 墳偏序集VA,R的哈斯圖如F.B為A的升集.共中日=f仇.城；!與出R的關(guān)宓表達(dá)式;2,凱出關(guān)系R的關(guān)系圖，3求出H的最大元,極大元.上界.16. 1殳圖 GV = (納 gs Mg )Eu叫fV I)> C v . th ) >.試口 兩出 【；的圖形表示j2 寫出其鄰樓用陣；3 求出每個(gè)苗點(diǎn)的度數(shù)，4 畫出圖G的樸踞的胡形.17. 求P-QAK的合取范式與主合取范式.六、證明題此題共8分 18. 設(shè)A./3電任意集合.試訕明，看A = B.試題答案及評(píng)分標(biāo)準(zhǔn)供參考 一、項(xiàng)選捧H每小 3分，本聘共15分 I. A2. A3LCZ.W2HB小H 3分.本JS共15分 G96.1也6.lO.Al VACZ>VA3 V.41 三, 邏Ml公每小趣6分.本贓共I2分 1L設(shè)ZS昨天TW.2分SH佑日公式為必傍分 12. 設(shè)P小王今天上午去看電物Q,小王今天上午去打璋2分 峭命12公式丸rP-Q>.或哲<rpAQ>V【PA rQ 6 分 四、判唏說(shuō)明18每小18 7分，本Jg共H分 13. 正確，【3分 例，設(shè)5 分 WIW AB 且 AC&*7 分說(shuō)明I畢山襯合條件的例均靖分.1，正嘛3分 完全兇K.燧平面圈. _如K.可成611F圖示城人平而.【7分五、計(jì)»«(«小部12分，此題矣36分)15. <l)W=<a.a>.<6.6>.<c .c>.< J .</>.<a .6>. <a .>. <u/>)(4 分>3】關(guān)系圖8分 3 集合B無(wú)最大元，耿太元為心與。無(wú)上界-2分 16. M：H 關(guān)系圖3分 2 鄰樓平警 O dc«vj =3dcg vt «2<1心頃。=2dc&M = 29分 coibffl<12 分、17. PTQRR«-PVCQAK>2分 DT r P V Q> A【r P V R 合取范式5分】m-PVQ>VR/ rR A【r PVR 3分】f VQ> V【A A F> Ap VR VQAQ 9分,DiU'VQVR /H *PVQV - ADACPVKVQJAC-F VKV-'Q "1 分，qrVVQVR 人rPVQV R A，PV，QVR 主合取他式32 分 大ii明18本H共M分 10證奶.» z6A.H»<j .a>6AxA.<1 分 因 AXA-HXH.故 V ,r ,x> HXH.WJff rGB.<3 分 侃此AGH.心分 段 了68,WKx>6HXH.C6 分，W A X4ft 2G4.1M 此 BG .A.7 分 故W A-B.X8 分