離散數(shù)學(xué)試卷七試題與標(biāo)準(zhǔn)答案

1、個人收集整理僅供參考學(xué)習(xí)試卷七試題與答案一、填空1、 n 階完全圖Kn 地邊數(shù)為 .2、 右圖地鄰接矩陣A= .3、 完全二叉樹中，葉數(shù)為nt，則邊數(shù) m= .4、 設(shè) < a,b,c, * >為代數(shù)系統(tǒng)， * 運算如下：則它地幺元為；零元為；abc*a、 b、c 地逆元分別為 .aabc(G) ，最小點度(G)5、任何圖地點連通度(G)，邊連通度地關(guān)系為bbac.cccc6、在具有 n 個結(jié)點地有向圖中，任何基本通路地長度都不超過 .7、結(jié)點數(shù) n（ n3 ）地簡單連通平面圖地邊數(shù)為m，則 m 與 n 地關(guān)系為 .8、若對命題 P 賦值 1，Q 賦值 0，則命題 PQ 地真值為

2、.9、命題“如果你不看電影，那么我也不看電影”（P：你看電影， Q：我看電影）地符號化為.10、若關(guān)系 R 是等價關(guān)系，則 R 滿足性質(zhì) .二、選擇1、 左邊圖地補(bǔ)圖為（）.2、 對左圖 G，則 k (G),(G ),(G ) 分別為（） .1 / 8個人收集整理僅供參考學(xué)習(xí)A、 2、 2、2； B、 1、 1、2； C、2、 1、 2； D、1、2、2 .3、 一棵無向樹 T 有 8個頂點， 4 度、 3 度、 2 度地分枝點各 1 個，其余頂點均為樹葉，則T 中有（）片樹葉 .A、 3；B、 4；C、 5；D 、64、 設(shè) <A ，+，·>是代數(shù)系統(tǒng)，其中+ ，

3、83;為普通地加法和乘法，則A= （）時 <A ，+，·>是整環(huán) .A 、 x | x2n,nZ ；B、 x | x 2n 1,nZ ；C、 x | x0,且xZ ；D、 x | x a b4 5, a, b R .5、 設(shè) A=1 ， 2， ， 10 ，則下面定義地運算* 關(guān)于 A 封閉地有（） .A 、 x*y=max(x ,y)；B、x*y= 質(zhì)數(shù) p 地個數(shù)使得 xpy ；C、x*y=gcd(x , y)； (gcd (x ,y) 表示 x 和 y 地最大公約數(shù) )；D、 x*y=lcm(x ,y)（lcm(x ,y)表示 x 和 y 地最小公倍數(shù)） .6、如果解

4、釋 I 使公式 A為真，且使公式 AB 也為真，則解釋I使公式 B為（）.A、真；B 、假；C、可滿足；D、與解釋 I 無關(guān) .7、設(shè) Aa,b，則 P（A）×A = （）.A、A ；B、P（A）；C、D、, a,b, a, a, a, b, b, a, b, b,A, a,A,b；a,b,a, a,b, a,a, b,b, b,a, A,b, A.8、設(shè)集合 A ，B 是有窮集合，且A m , B n ，則從 A 到 B 有（）個不同地雙射函數(shù) .A、 n； B 、 m ；C、 n! ；D 、 m! .9、設(shè) K = e , a , b , c ，K ,是 Klein 四元群，則元

5、素a 地逆元為（） .A 、 e ；B 、a ；C、b ；D 、c.10、一個割邊集與任何生成樹之間（）.A 、沒有關(guān)系；B 、割邊集誘導(dǎo)子圖是生成樹；C、有一條公共邊；D 、至少有一條公共邊.三、計算1、通過主合取范式，求出使公式(PQ)R 地值為 F 地成真賦值 .2、設(shè) A 2，3，4，9 ， B2，4，7，10 ,12 ，從 A 到 B 地關(guān)系R a , b a A , bB , 且 a 整除 b ，試給出 R 地關(guān)系圖和關(guān)系矩陣， 并說明此關(guān)系是否為函數(shù)？為什么？3、設(shè) S = R - -1 （ R 為實數(shù)集）， aba bab .（1）說明S,是否構(gòu)成群；（2）在 S 中解方程 2

6、 x3 7 .4、將公式( PQ) R）( PR) 劃為只含有聯(lián)結(jié)詞， 地等價公式 .5、設(shè) A x1 , x2 , x3 , x4 , x5 ，偏序集A, R地 Hass 圖為2 / 8個人收集整理僅供參考學(xué)習(xí)求A 中最小元與最大元； x3 , x4 , x5 地上界和上確界，下界和下確界.四、證明n2m1、設(shè) G 是（ n,m ）簡單二部圖，則4 .m1 (n 1)( n 2)2、設(shè) G 為具有 n 個結(jié)點地簡單圖，且2則G是連通圖 .3、設(shè) G 是階數(shù)不小于11 地簡單圖，則G 或 G 中至少有一個是非平圖 .4、用構(gòu)造證明法證明 A(B C)，(EF )C，B (AS) B E.五、生

7、成樹及應(yīng)用1、如下圖所示地賦權(quán)圖表示某七個城市v1 ,v2 , , v7 及預(yù)先測算出它們之間地一些直接通信線路造價，試給出一個設(shè)計方案，使得各城市之間既能夠通信而且總造價最小.b5E2RGbCAP2、）構(gòu)造 H、 A 、P、N 、 E、W 、 R、對應(yīng)地前綴碼，并畫出與該前綴碼對應(yīng)地二叉樹， 寫出英文短語HAPPYNEWYEAR 地編碼信息.p1EanqFDPw六、對于實數(shù)集合R，在下表所列地二元遠(yuǎn)算是否具有左邊一列中地性質(zhì)，請在相應(yīng)位上填寫“Y”或“ N ”.MaxMin+可結(jié)合性可交換性存在幺元存在零元答案一、填空010100111 n(n1)01000110； 3、 2(nt1) ；

8、4a， c，a、 b、沒有1、 2； 2、3 / 8個人收集整理僅供參考學(xué)習(xí)5、n-1； 6、 (G)(G )(G ) ；7、 m3n6 ；8、0；9、 PQ ；10、 5、自反性、對稱性、傳遞性；二、選擇題目12345678910答案AACDA ，CACDBD三、1. 解：原式(PQ)R(PQ)R(P R)(QR)( PQR)(PQR) (PQR)(PQR)M 100M 110M 010使公式(PQ)R 地值為 F 地成真賦值為：P :1P :1P :0Q :0Q :1Q :1R: 0； R:0； R: 0.2解：R 2, 2, 2,4,2 ,10,2,12,3,12,4 , 4,4,12

9、則R 地關(guān)系圖為：ABR 地關(guān)系矩陣為11011220000134M R10017040000010關(guān)系 R 不是 A 到 B 地函數(shù)，因為9元素 2， 4 地象不唯一（或元素9無象）.123、解：（ 1）1）a,bS易證abababS ，即運算 * 是封閉地 .2）a,b,cS( ab)c(abab)cababc(abab)cabcabacbc abc,而a(bc)a(bcbc )a(bcbc)a(bc bc)abcbcabacabc,(a b) c a(bc) ，即 * 可結(jié)合 .3）設(shè) S 關(guān)于 * 有幺元 e，則a S , e a a e a .而 a e e a a e ea a ,

10、e 0.4）aS 設(shè)有逆元 a1.則 aa 1a 1ae ，4 / 8個人收集整理僅供參考學(xué)習(xí)即 a a 1aa 1a 1aS 中任意元都有逆元，綜上得出，0 ，1 a ，即S,構(gòu)成群 .（2）由 2x 32x 32x3x66x12x117 ，x13 .4、解：原式( PQ)R)(PR)(PQ)R(P R)( ( PQ)R(PR) .5、解： A 中最大元為 x1 ，最小元不存在； x3 , x4 , x5 上界 x1 ,x3 ，上確界 x1；下界無，下確界無 .四、 證明i.設(shè) G=（ V， E）， VX Y , Xn1, Y n2,則 n1n2 nm n1 n2 n1 (n n1 )n12

11、n1n(n1n) 2n 2對完全二部圖有24nn2n當(dāng)2 時，完全二部圖 ( n , m) 地邊數(shù) m 有最大值 4 .1n2m4 .故對任意簡單二部圖 (n , m) 有ii.反證法：若 G 不連通，不妨設(shè)G 可分成兩個連通分支G1 、G2，假設(shè) G1 和 G2 地頂點數(shù)分別為 n和 n ，顯然 n1n2n DXDiTa9E3d12.n11 n21n1n 1 n2n 1mn1 (n11)n2 (n21)(n1)(n1n22)( n1)( n2)2222與假設(shè)矛盾 .所以 G 連通 .3、（1）當(dāng) n=11 時， GGK11 Km'11105511 邊數(shù)2條，因而必有 G 或 G 地邊

12、數(shù)大于等于28，不妨設(shè) G 地邊數(shù) m28 ，設(shè) G 有 k 個連通分支，則G 中必有回路 . （否則 G 為 k 棵樹構(gòu)成地森林，kk每棵樹地頂點數(shù)為 ni，邊數(shù) mi，則 mini1,i1k ,nin11,mi mi 1i 1RTCrpUDGiTkk28mmi(ni1)nk11 k矛盾）i 1i1下面用反證法證明G 為非平面圖 .假設(shè) G 為平面圖，由于G 中有回路且 G 為簡單圖，因而回路長大于等于3 .于是 G 地每個面至少由 g5 / 8個人收集整理僅供參考學(xué)習(xí)mg(n k1)g2( g 3)條邊圍成，由點、邊、面數(shù)地關(guān)系，得： 5PCzVD7HxA28 mg(11 k 1)3(11

13、(k1)3(11(11) 31132 27g231而 28 27 矛盾，所以 G 為非平面圖 .（ 2）當(dāng) n>11 時，考慮 G 地具有 11 個頂點地子圖 G ' ，則 G ' 或 G ' 必為非平面圖 .如果 G ' 為非平面圖，則 G 為非平面圖 .'如果 G 為非平面圖，則 G 為非平面圖 .4、證明：（1） BP(附加前提 )（2） B(AS) 前提引入(3) AS (1)(2) 假言推理(4)A(3)化簡(5)ABC 前提引入(6)BC(4)(5) 假言推理(7)C(6)化簡(8)( EF )C 前提引入(9)(EF )(7)(8)

14、拒取式(10)EF(9)置換(11)E(10)化簡五、 樹地應(yīng)用1、解：用庫斯克（Kruskal ）算法求產(chǎn)生地最優(yōu)樹.算法略 .結(jié)果如圖：樹權(quán) C(T)=23+1+4+9+3+17=57即為總造價五、由二叉樹知6 / 8個人收集整理僅供參考學(xué)習(xí)H、A 、P、 Y、 N、E、 W、 R 對應(yīng)地編碼分別為000、001 、010 、011、100 、101、 110、111.顯然 000 ，001 ，010，011，100， 101， 110， 111 為前綴碼 .英文短語 HAPPY NEW YEAR地編碼信息為000 001 010 010 011 100 101 001 001 101 0

15、01 111六、MaxMin+可結(jié)合性YYY可交換性YYY存在幺元NNY存在零元NNN版權(quán)申明本文部分內(nèi)容，包括文字、圖片、以及設(shè)計等在網(wǎng)上搜集整理.版權(quán)為個人所有This articleincludessome parts,includingtext,pictures,and design. Copyright is personal ownership.jLBHrnAILg用戶可將本文地內(nèi)容或服務(wù)用于個人學(xué)習(xí)、研究或欣賞，以及其他非商業(yè)性或非盈利性用途， 但同時應(yīng)遵守著作權(quán)法及其他相關(guān)法律地規(guī)定，不得侵犯本網(wǎng)站及相關(guān)權(quán)利人地合法權(quán)利. 除此以外，將本文任何內(nèi)容或服務(wù)用于其他用途時，須征得本

16、人及相關(guān)權(quán)利人地書面許可，并支付報酬 . xHAQX74J0XUsers may use the contents or services of this article for personal study, research or appreciation, and other non-commercial or non-profit purposes, but at the same time,7 / 8個人收集整理僅供參考學(xué)習(xí)they shall abide by the provisions of copyright law and other relevant laws, and

17、shall not infringe upon the legitimaterights of this website and its relevant obligees. In addition, when any content or service of this article is used for other purposes, written permission and remuneration shall be obtained from the person concerned and the relevantobligee.LDAYtRyKfE轉(zhuǎn)載或引用本文內(nèi)容必須是以新聞性或資料性公共免費信息為使用目地地合理、善意引用，不得對本文內(nèi)容原意進(jìn)行曲解、修改，并自負(fù)版權(quán)等法律責(zé)任. Zzz6ZB2LtkReproduction or quotation of the content