1、文檔供參考，可復制、編制，期待您的好評與關(guān)注！ 離散1一、選擇題（每題2分，共20分）CABBB DACDA二、填空題（每題2分，共20分）1. 2.ab=1，ab=0 3.x*(xy)=x x(x*y)=x 4. 無回路5. 大項的合取所組成 6. ($x) P(x) (x) P(x)7.68.對任意的a,b,有(a*b)*(a*b)=(a*a)*(b*b)9. 10. ，,，,三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1. (5分）給定無孤立點圖G，若存在一條路，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉路；如果一個圖有歐拉路，則這個圖能一筆畫出。2. （8分）各4分，

2、步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式:（PQR）（PQR）（PQR）3. （5分）由無向樹的性質(zhì)可知，無向樹的頂點數(shù)是邊數(shù)加1，又知無向圖所有頂點的度之和為邊數(shù)的2倍。（1分）令1度頂點個數(shù)為x,則頂點數(shù)為2+1+3+x，所有頂點的度之和為x+2*2+3+3*4，（2分）從而有x+2*2+3+3*4=2*(2+1+3+x-1)，解之得x=9,即有9個1度的點。（2分）4. （7分）解：5. （5分）（2分）,（2分）,具有自反，對

3、稱性質(zhì)（1分）五、證明（3小題，共20分）1. （10分）每步約1分，沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）PRP（2）RPT（1）E（3）PQP（4）PQT（3）E（5）QSP（6）PST（4）（5）I（7）RST（2）（6）I（8）RST（8）E2. （5分）。證明：(AB)(AC)=(AB)(AC)=A(BC)=A(BC)=A(BC)3. （5分）證明過程：明顯，H是G的子集。任取xH,則有a*x=x*a，對等式左乘和右乘x-1,有x-1*a=a*x-1.再任取yH,則(y*x-1)*a=y*(x-1*a)=y*(a*x-1)=(y*a*)x-1=(a*y)*x-1=a*

4、(y*x-1)由定理可得，H是G的子群。或由群的定義來證明。離散2一、選擇題（每題2分，共20分）BCCADAABDC二、填空題（每題2分，共20分）1.(1)PQ(2)(PQ)(PQ)或（(PQ)(PQ)等）2.自反，反對稱，傳遞3.（）4.經(jīng)過圖中每邊一次且僅一次 5. 上確界 6.MaxMin+可結(jié)合性YYY可交換性YYY存在幺元NNN存在零元NNY7. 至少有兩個元素的有補分配格 8. 小項的析取所組成 9. x | (xA) (xB) 10. 簡單圖中若每一對結(jié)點間都有邊相連三、判斷題（每題1分，共10分） 四、解答題（3小題，共20分）1. （5分）在根樹中，若每一個結(jié)點的出度小于

5、或等于2，則這棵樹稱為2叉樹。任何一棵有序樹都可以改寫為對應的二叉樹，方法是：除了最左邊的分枝點外，刪去所有從每一結(jié)點長出的分枝。在同一層次中，兄弟結(jié)點間用從左到右的有向邊連接。選定二叉樹的左兒子和右兒子如下：直接處于給定結(jié)點下面的結(jié)點，作為左兒子，對于同一水平線上給定結(jié)點右鄰結(jié)點，作為右兒子，以此類推。2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:（PQR）（PQR）（PQR）主合取范式:（PQR）（PQR）（PQR）（PQR）（PQR）3.（7分）這是一個求最小生成樹的問題，可

6、用多種方法，但必須有思路和過程。解：按該圖的生成樹建立通訊線路能使城市間直接通訊，按最小生成樹建立通訊線路能使城市間直接通訊且總造價最小。（1分）通訊方案（最小生成樹）：（5分）最小總造價為：57（1分）五、證明（3小題，共30分）4. （10分）每步約1分，沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）PQP（2）QRP（3）QRT(2)E（4）PRT(1)（3）I（5）RP（6）PT（4）（5）I（7）SPP（8）ST(6)（7）I5. （10分）證明過程：證明：因為R和S都是非空集A上的等價關(guān)系，所以R和S都有自反性，對稱性和傳遞性。（1分）（1）,則,所以,所以RS是自反的。（

7、2分）（2），則，因為R和S是對稱的，所以（3分），從而,所以RS是對稱的。（3），則，因為R和S是傳遞的，所以，從而,所以RS是傳遞的。（3分）由上面的三點可得RS是A上的等價關(guān)系。（1分）6. （6分）證明過程：如果圖G(V,E)不連通的話，它的頂點可以分為兩個非空集合A,B，其中對于任意在A中的點P和任意在B中的點Q都沒有PQ這條邊。（3分）取其補圖，則對于任意在A中的點P和任意在B中的點Q都有PQ這條邊。這樣的話，對于任意兩點P,Q，如果它們分別處于A,B的話，它們之間就有邊相連；否則，不失一般性設(shè)它們都在A中，由于B非空，我們可以在B中任取一點R，我們知道PR和QR這兩條邊都是存在的

8、，所以P,Q是連在一起的。綜上，知連通。（3分）4（4分）證明過程：證明：顯然，*運算封閉，且(a*b)*c=a*(b*c)=a+b+c-4,所以*滿足結(jié)合律。（2分）2是幺元，4-a是a的逆元。所以是群。（2分）離散3一、選擇題（每題2分，共20分）CCAAD DBDAB二、填空題（每題2分，共20分）1（1）PQ，（2）（PQ）(PQ)2.F3.不相等4.x和y的最大公約5.6.永真公式 給定一個命題公式，若無論對分量作怎樣的指派，其對應的真值永為T，則稱該命題公式為重言式。 7. 經(jīng)過圖中每邊一次且僅一次 8. |xXzZ($y)(yYRS) 9. G中的任意元素都由a的冪組成 10.

9、邊界的回路長度三、判斷題（每題1分，共10分） 四、解答題（4小題，共30分）1. （5分）設(shè)P是謂詞（1）全稱量詞消去規(guī)則，簡稱US規(guī)則：(x)P(x)P(c) ，c為個體域中某個任意的客體； （2）全稱量詞引入規(guī)則，簡稱UG規(guī)則：P(x) (x)P(x)；（3）存在量詞消去規(guī)則，簡稱ES規(guī)則：($x)P(x) P(c)，這里c是論域中的某些客體。（4）存在量詞引入規(guī)則，簡稱EG規(guī)則：P(c) ($x)P(x)，這里c是論域中的一個客體。2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范

10、式:(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式:(PQR)(PQR)(PQR)3.（10分）哈斯圖4分,其它各2分.R的哈斯圖:集合A:最大元素為無、極大元素為24,36、下界為無、上確界為無。集合B:最大元素為12、極大元素為12、下界為2,3,6、上確界為12。集合C:最大元素為6、極大元素為6、下界為無、上確界為6。4.（7分）最優(yōu)二叉樹5分,最佳前綴碼方案1分,編碼信息1分解：根據(jù)字母出現(xiàn)的頻率得出字母對應的最優(yōu)二叉樹和各字母的編碼:傳輸它們的最佳前綴碼方案:w:0000,p:0001,a:001,r:010,y:011,h:10,e:110,n:111.happyn

11、ewyear的編碼信息:1000100010001011111110001010五、證明（3小題，共20分）1. （8分）每步約1.5分,沒有P,T標識扣3分,沒有序號扣3分。證明過程：(1)EP(2)EFT(1)I(3)(EF)DP(4)DT(2),(3)I(5)BDP(6)BT(4),(5)I2. （6分）證明過程：設(shè)平面圖的結(jié)點數(shù)為v,邊數(shù)為e,面數(shù)為r,則有歐拉公式成立：v-e+r=2.（1分）本題中，v=6,e=12,從而r=8.（1分）根據(jù)定理，所有面和次數(shù)之和為邊數(shù)的2倍。而邊數(shù)為12,所以8個面的次數(shù)之和為24.（1分）每個面的次數(shù)至少為3,要8個面的次數(shù)之和為24.每個面的次

12、數(shù)只能為3.（2分）3. （6分）證明過程：證法（1）：證明在運算+上封閉性對于任意，設(shè)=2，=2， 則+=2+2=2（+） 說明在運算+上封閉。 (4分)又I 是的子群 (得2分)證法（2）：I 證明是一個群（1）封閉性： ，有=2，=2，+=2（+） (1.5分)（2）結(jié)合律： （+）+=2（+）=+（+） (1.5分)（3）幺元： +0=0+=0 0是幺元 (1.5分)（4）每一個元素都有逆元： x,由 x-x=0，得x的逆元為-x。(1.5分)離散4一、選擇題（每題2分，共20分）CDACA DBABB二、填空題（每題2分，共20分）1.P Q，(PQ)(PQ)(或(PQ)(PQ),(

13、PQ)2.2n3.4. 5.歐拉回路 6. *x=x*= 7. ($x)P(x) P(c) 8. IA 9. 良序集 10. V V ，E E三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1（5分）（1）置新矩陣A=M（2）置i=1（3）對所有j如果Aj, i =1，則對k=1,2,nAj,k=Aj,k+Ai,k（4）i= i+1（5）如果 i n,則轉(zhuǎn)到步驟（3）,否則停止。2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQR)(PQR)(

14、PQR)(PQR)(PQR)主合取范式:PQR3（4分）U=a,b,c,d,e, A=a,d, B=a,b,c。求P(A)-P(B)解：P(A)=,a,d,a,d,P(B)=,a,b,c,a,b,a,c,b,c,a,b,c（2分）P(A)-P(B)=d,a,d（2分）4.（9分）解：(1) （4分）(2) 前綴碼對應的二叉樹T為（3分）前綴碼：2：0001，3：0001，5：001，7：010，8：011（2分）5. （4分）解：令ac=a,ad+b=b得，c=1,d=0,即幺元為 （2分）令*=得，ac=1,ad+b=0所以c=1/a, d=-b/a,從而-1= （2分）五、證明（2小題，共

15、20分）7. （10分）每步約2分，沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）P(QR)P（2）R(QS)P（3）(QR)ST(2)E（4）(QR)(QS)T(3)E（5）P(QS)T(1)(4)I8. （10分）證明： aA則有a *a =ea*b=a*c *a*b=*a*c e*b=e*c b=c (4分)已知*e=e*e=e= 由的結(jié)論得 x*e=x,e是幺元 (2分)是半群,滿足封閉性與結(jié)合律,則只需證明每一個元素都有逆元. =e*=*e又由的結(jié)論得 =x*=e x的逆元 為群 (4分)離散5一、選擇題（每題2分，共20分）CADAC DBCBA二、填空題（每題2分，共20

16、分）1（1）PQ，（2）（PQ）(PQ)2.F T3. a4，a5，a6，a7,a84. ,5.n-16.有零個或兩個奇數(shù)度結(jié)點7.b*a=a*b=e8.P(c) ($x)P(x) 9.對于每一個xX,有唯一的yY，使得f10.圖G的子圖G包含G的所有結(jié)點三、判斷題（每題1分，共10分） 四、解答題（5小題，共3029分）1（5分）若把一個集合A分成若干個非空子集，使得A中每個元素屬于且僅屬于一個分塊，這些分塊的全體叫做A的一個劃分。設(shè)A的一個劃分為：，則就是由這個劃分確定A的元素間的一個等價關(guān)系。2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，

17、且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQR)(PQR)主合取范式:(PQR)(PQR)(PQR)(PQR)3（4分）解：A-B=d,B-C=a,c(2分)(A-B)(B-C)= a,c,d(2分)4.（7分）解：八進制數(shù)字出現(xiàn)的頻率已從小到大排列,由這些頻率求出最優(yōu)二叉樹為下右圖，： 由最優(yōu)二叉樹樹葉對應最優(yōu)前綴碼：.(2分) (3分)各八進制數(shù)字對應最優(yōu)前綴碼為:7:0001,6:0000,5:1111,4:1110,3:110,2:001,1:10,0:01 (2分)5.（6分）解：這是一個頂點著色問題的應用。將頂點的度從大到小排列得到：v

18、3:6,v9:5,v7,v8:4,v1,v2,v4,v5,v6:3。將v3著顏色1,v9著顏色2，v7著顏色1,v8著顏色3,v1著顏色2,v2著顏色3,v4著顏色2,v5著顏色1,v6著顏色2,因而圖是3可著色的。即可以用3天考完所有考試。將v9著顏色1,v3,v7著顏色2，v1著顏色1,v2著顏色3,v4著顏色1,v5著顏色2,v6著顏色1,因而圖是3可著色的。即可以用3天考完所有考試。五、證明（2小題，共20分）4. （10分）每步約1.5分,沒有P,T標識扣3分,沒有序號扣3分。證明過程：(1) RSP(2)SRT(1)E(3)PRP(4)RPT(3)E(5)PQP(6)RQT(4),

19、(5)I(7)SQT(2)(6)I5. （10分）證明過程：要證明R是自反的，對稱的和傳遞的，R才是等價關(guān)系。（1分）（1）,因為a+b=a+b,所以，所以R是自反的。（2分）（2），則從而，所以R是對稱的。（2分）（3），則a+d=b+c,c+f=d+e,將上式左右相加得a+f=b+e,即,所以R是傳遞的。（2分）綜上所述，R是等價關(guān)系。（1分）R是一個等價類集合，由和有關(guān)系的元素構(gòu)成。（1分）R=,（1分）離散6一、選擇題（每題2分，共20分）DACBC ADCBD二、填空題（每題2分，共20分）1.PQ，(PQ)(PQ)(或(PQ)(PQ),(PQ)2.P=T，Q=F3.A的覆蓋有S1，

20、S2，S3，S4，S5，A的劃分有S3，S4，S54.b5.，n-16.所有結(jié)點度數(shù)為偶數(shù)7. ，8.IA9.對于所有xA和 xC有f(x)=g(x) 10.若存在一條路三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1（5分）哈斯圖是簡化的偏序關(guān)系圖，具體畫法如下：（1）用小圓圈代表元素；（2）若x y，x y，將代表y的小圓圈放在代表x的小圓圈之上，（3）如果 COVA，則在y與x之間用直線連接。2.（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR

21、)(PQR)主合取范式:(PQR)(PQR)(PQR)(PQR)(PQR)3.（6分）這是一個求最小生成樹的問題，可用多種方法，但必須有思路和過程。解：按該圖的生成樹建立通訊線路能使城市間直接通訊，按最小生成樹建立通訊線路能使城市間直接通訊且總造價最小。（2分）通訊方案（最小生成樹）：（3分）最小總造價為：18（1分）4.（7分）如果前綴碼是其它的方案，只要思路正確，也給滿分。解：H：000，A：001，P：010，N：011，E：100，W：101，R：110，Y：111（2分）該前綴碼對應的二叉樹：（3分）英文短語HAPPYNEWYEAR的編碼信息：00000101001011101110

22、0101111100001110（2分）5（4分）直接寫出結(jié)果給2分解：AB=b,c,d,(AB)C=b,d五、證明（2小題，共20分）9. （10分）每步約1分，沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）A P(附加前提)（2）AB T I（3)ABCD P（4)CD T(2)(3) I（5)D T(4) I（6)DE T(5) I（7)DEF P（8)F T(6)(7) I（9)AF CP10. （10分）證明過程：（1）對于任意a,bR-1若a*b=a+b+ab=-1，則有a=(-1-b)/(1+b)=-1，與a R-1矛盾。*運算滿足封閉性 （2分）（2）對于任意a,b,c

23、R-1有 (a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c =a+b+c+ab+ac+bc+abc 而a*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc) =a+b+c+bc+ac+ab+abc (a*b)*c=a*(b*c)*運算滿足結(jié)合性 （2分）（3）設(shè)對任意元素aR-1，則有a*0=a+0+a0=a0*a=0+a+0a=a即有 a*0=0*a=a 0是幺元 （2分）（4）對于任意a,bR-1設(shè)a*b=a+b+ab=0，則有b(1+a)=-ab=-a/(1+a)也就是a(-a/(1+a)=0這說明任意aR-1,a有逆元-a/(1+a)。（3

24、分）由于中*運算封閉，滿足結(jié)合律，有幺元，任意元素有逆元，所以是群離散7一、選擇題（每題2分，共20分）BDCAB CADBC二、填空題（每題2分，共20分）1（1）PQ，（2）（PQ）(PQ) 2.T3.C4.k5.每條邊一次且僅一次6.經(jīng)過圖中的每一個結(jié)點恰好一次7.封閉的和可結(jié)合的8.A1 A2 An，（n1）其中A1，A2 ，An都是由命題變元或其否定所組成的析取式。9.x*y=y*x10.圖G=V,E的任意兩個結(jié)點皆有路連通三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1（5分）若把一個集合A分成若干個非空子集，使得A中每個元素屬于至少屬于一個分塊，這些分塊的全體叫

25、做A的一個覆蓋。設(shè)A的一個覆蓋為：，則就是由這個劃分確定A的元素間的一個相容關(guān)系。2（3分）解：=0,2(1分)R=,(2分)3（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQR)(PQR)主合取范式:(PQR)(PQR)(PQR)(PQR)4.（10分）解：關(guān)系矩陣:關(guān)系圖: （4分）求的傳遞閉包t(R)有二種矩陣運算方法：（1）矩陣冪方方法：，所以（4分）(2)Warshall方法：所以（4分）的傳遞閉包t(R)= , （2分）5.（6分）解：這是一個頂點

26、著色問題的應用。（1分）將頂點的度從大到小排列得到：v9:5,v3:4,v7,v4:4,v1,v2,v5,v8,v6:3。（2分）將v9著顏色1,v3,v7著顏色2，v4著顏色1,v1著顏色1,v2著顏色3,v5著顏色2,v8著顏色3,v6著顏色3,因而圖是3可著色的。（2分）即可以用3天考完所有考試。（1分）五、證明（2小題，共20分）1. （10分）每步約1.5分,沒有P,T標識扣3分,沒有序號扣3分。證明過程：(1)BDP(2)BDT（1）E(3)(CA)DP(4)D(CA)T（3）E(5)B(CA)T（2）（4）I(6)B(CA)T（2）（4）I(7)（BC）（BA)T（5）E(8)B

27、CT(6)I2. （10分）證明過程：（1）對任意A,由于xy=yx，有,R所以R具有自反性。（3分）（2）對任意，R,有xv=yu，即uy=vx從而有，R所以R具有對稱性。（3分）（3）對任意，R，R,有xv=yuuz=vw,xz=yw,由定義得，R所以R具有傳遞性。（3分）由于R具有自反性，對稱性和傳遞性，所以R是等價關(guān)系。（1分）離散8一、選擇題（每題2分，共20分）ABCDD BDACA二、填空題（每題2分，共20分）1（1）P Q （2）PQ 2.T 3.a b c d 4. n-15.經(jīng)過圖中的每一個結(jié)點恰好一次6.幺元7. (x)(xAxB) 8.RIA9.x*yA10.單側(cè)三、

28、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1（5分）（1）關(guān)于R的全體不同的等價類為元素的集合 aR| aA稱為A關(guān)于R的商集，記為A/R。（3分）（2）把彼此有關(guān)系的元素放在一個集合中，由這些集合組成一個集合就是關(guān)于R的商集。（2分）2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQR)主合取范式:(PQR)(PQR)(PQR)(PQR)(PQR)3（10分）解：關(guān)系矩陣:關(guān)系圖: （4分）求的傳遞閉包t(R)有二種矩陣運算方法：（1）矩陣

29、冪方方法：，所以（4分）(2)Warshall方法：所以（4分）的傳遞閉包t(R)=,（2分）4.（3分）解：R=, (3分)5.（4分）解：RR=, （2分）Rc=,（4分）五、證明（3小題，共20分）3. （8分）每步約1.5分,沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）R P（2） QR P （3） Q T（1）(2) （4） (PQ) P（5） PQ T(4)E（6） P T(3)(5)I4. （6分）最優(yōu)樹為：（3分）W（T）=(1+2+1+1)4+(2+3)3+(4+5)2=53（3分）5. （6分）證明：有,使得,對,有,使得因而*e)=()*e=e*e=e= (3分

30、)上式左邊同時乘以得()*(x*e)=()*x即e*(x*e)=e*x,也就是x*e=x e是右幺元,從而e是幺元。 離散9一、選擇題（每題2分，共20分）ACBDD AACAB二、填空題（每題2分，共20分）1.2. 3. b4.具有漢密爾頓回路5.（1）運算*是封閉的。（2） 運算*是可結(jié)合的。（3） 存在幺元e。（4） 對于每一個元素xG,存在著它的逆元x-16.析取式中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。7.若AB,且BC, 則AC8.RRc9.(x*y)*z=x*(y*z)10. 強連通圖三、判斷題（每題1分，共10分）四、解答題（5小題，共29分）1（5分）

31、封閉性：A中的每個元素都在運算表中；可交換性：運算表關(guān)于主對角線是對稱的；等冪性: 運算表中主對角線中的元素等于它所在行和列的表頭元素；零元：該元素所在行和所在列的元素值都與該元素相同；幺元: 該元素所在的行和列依次與運算表中的行和列相同。 2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。主析取范式：(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式：(PQR)(PQR)(PQR)3（4分）RR的關(guān)系矩陣（2分）R-1的關(guān)系矩陣:（2分）4（8分）(6分)W(T)=2*4+3*4+5*3+

32、9*2+7*2+8*2=83(2分)5.（5分）這是一個求最小生成樹的問題，可用多種方法，但必須有思路和過程。解：按該圖的生成樹建立公路能使城市間有公路連通，按最小生成樹建立公路能使城市間有公路連通且總造價最小。（1分）最優(yōu)化的設(shè)計方案:（4分）公路長：9（1分）五、證明（3小題，共24分）1（10分）每步約1.5分,沒有P,T標識扣3分,沒有序號扣3分。證明過程：證法1 （1） P（2）T(1)E（3)P（4)T(3)E（5)T(2)(4)I（6)P（7)T(5)(6)I法2 （1）P(附加前提)（2）P（3)T(2)E（4)QT(1)(3)I（5)P（6)RT(4)(5)I（7)P（8)S

33、T(6)(7)I（9)CP2（10分）（1） （1分）（2）r(R)=RIA=, （2分）S(R)=RRc=, （2分）t(R)=RR2R3R4=,，, （3分） 也可用Warshall算法計算t（R）。（3）包含R的最小的等價關(guān)系=r(R)S(R)t(R)=,，,IA離散10一、選擇題（每題2分，共20分）AABCD CBDCB二、填空題（每題2分，共20分）1（1）P Q，（2）（PQ）(PQ) 2.a ca b3.2,4 和4.e=v-15.任何兩條邊除了端點外沒有其它的交點6.ab-1S7. 對任意素數(shù)x，總存在奇數(shù)y，使得y可以整數(shù) 8.RR2R39.x*(yz)=(x*y)(x*z

34、) (yz)*x=(y*x)(z*x) 10.弱連通的三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1（5分）設(shè)是一個代數(shù)系統(tǒng)，其中G是非空集合，*是G上一個二元運算，如果（1） 運算*是封閉的。（2） 運算*是可結(jié)合的。（3） 存在幺元e。（4） 對于每一個元素xG,存在著它的逆元x-1。則稱是一個群。2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:( PQR)(PQR)(PQR)主合取范式:( PQR)(PQR)(PQR)(PQR)(PQR)3（4分）解：P(A

35、)=(2分)P(A)A=,(2分)4.（5分）解：R=,（2分）RR=,（2分）R-1=,（1分）5.（8分）若傳遞a ，b， c， d ，e， f 的頻率分別為2%， 3% ，5 %， 7% ，8% ，9%求傳輸它的最佳前綴碼。解：這是一個求最優(yōu)二叉樹問題。（1分）頻率最優(yōu)二叉樹（3分）字符最優(yōu)二叉樹（2分）最佳前綴碼：a:0000,b:0001,c:001,d:01,e:10,f:11（2分）五、證明（3小題，共20分）6. （8分）每步約0.8分,沒有P,T標識扣3分,沒有序號扣3分。證明過程：(1)AP(附加條件)(2)A(BC)P(3)BCT（1）（2）I(4)(CD)EP(5)G(

36、DE)P(6)(CD)ET(4)E(7)C(DE)T(6)E(8)(DE)GT（5）E(9)CGT(7)(8)I(10)BGT(3)(9)I(11)A(BG)CP7. （8分）證明過程：證明：充分性證明：設(shè)對任意有因為 所以即得：因此，群是阿貝爾群。（4分）必要性證明：設(shè)是阿貝爾群，則對任意有，因此 （4分）8. （4分）證明過程：解：a的等價類aR =a,b （2分）A/R=a,b，c，d，e,f （2分離散11一、選擇題（每題2分，共20分）BACDB ACACD二、填空題（每題2分，共20分）1. 所有子集為元素 2. S1S2 SmA 3. x (xB y x) 4. 可交換的 5.

37、不含有平行邊和環(huán)的圖 6. 結(jié)點 邊 7PQ （PQ）(QP）8. SiSj=，（這里ij）9.10.三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）6. （5分）設(shè)A ，R A A，若R是自反的、反對稱的和傳遞的，則稱R是A上的偏序關(guān)系。設(shè)為偏序集，BA，若存在yB，使得x (xB x y)為真，則稱y為B的最大元；若存在yB，使得x (xB y x x = y)為真，則稱y為B的極大元。7. （8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQ

38、R)(PQR)(PQR)(PQR)主合取范式:(PQR)(PQR)8. （7分）解：9. （5分）（2分）,（2分）,具有自反，對稱性質(zhì)（1分）10. （5分）3個2度頂點、1個3度頂點、2個4由無向樹的性質(zhì)可知，無向樹的頂點數(shù)是邊數(shù)加1，又知無向圖所有頂點的度之和為邊數(shù)的2倍。（1分）令1度頂點個數(shù)為x,則頂點數(shù)為3+1+2+x，所有頂點的度之和為x+3*2+3+2*4，（2分）從而有x+3*2+3+2*4=2*(3+1+2+x-1)，解之得x=7,即有7個1度的點。（2分）五、證明（3小題，共20分）11. （10分）每步約1分，沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）PRP

39、（2）RPT（1）E（3）PQP（4）PQT（3）E（5）QSP（6）PST（4）（5）I（7）RST（2）（6）I（8）RST（8）E12. （5分）。證明：“”必要性：已知CA，即xC，則有xA，此時有AC=A (AB) C=(AC) (BC)=A (BC) （2.5分） “” 充分性： 已知(AB) C=A (BC） 設(shè)任意的xC，則xC(AB) xA(BC) xA CA （2.5分）13. （5分）證明過程：明顯，H是G的子集。任取xH,則有ax=xa，對等式左乘和右乘x-1,有x-1a=ax-1.再任取yH,則(yx-1)a=y(x-1a)=y(ax-1)=(ya)x-1=(ay)x

40、-1=a(yx-1)由定理可得，H是G的子群。離散12一、選擇題（每題2分，共20分）CCABD BBDCA二、填空題（每題2分，共20分）1.a,b2. 3.SS45. x*x=x 6. ， 7. 假設(shè)A為T時，說明B也為T。假設(shè)B為F時，說明A也為F。8. 如果對于任意的x,y,zA, 每當xRy， yRz 時就有xRz 或(x)(y)(z)(xAyAzAxRy yRz xRz) 9. (a*b)*(a*b)=(a*a)*(b*b) 10. 諸邊所構(gòu)成的回路三、判斷題（每題1分，共10分） 四、解答題（3小題，共20分）1（5分）哥尼斯堡七橋問題：哥尼斯堡城市有一條橫貫全城的河，河中有二個

41、小島，河二岸與第一個小島各用二座橋連接，河二岸與第二個小島各用一座橋連接，小島與小島用二座橋連接。每逢假日，城中的居民進行環(huán)城的逛游，這樣就產(chǎn)生一個問題，能不能設(shè)計一次“逛游”，使得從某地出發(fā)對每座跨河橋走一次，而在遍歷了七橋之后卻又能回到原地。哥尼斯堡七橋問題沒有解，因為該問題可以變?yōu)榕袆e一個有4個頂點7條邊的連通圖是不是歐拉圖，由于該圖不是每個頂點的度都是偶數(shù)，所以不是歐拉圖。2（8分）各4分，步驟對，結(jié)果錯，適當扣分，如果求出其一個，另一個直接寫出，也不扣分。只有結(jié)果，且結(jié)果對，給一半分，只有結(jié)果，且結(jié)果錯，不給分。解：主析取范式:(PQR)(PQR)(PQR)(PQR)主合取范式:(P

42、QR)(PQR)(PQR)(PQR)3.（7分）這是一個求最小生成樹的問題，可用多種方法，但必須有思路和過程。解：按該圖的生成樹建立通訊線路能使城市間直接通訊，按最小生成樹建立通訊線路能使城市間直接通訊且總造價最小。（1分）通訊方案（最小生成樹）：（5分）最小總造價為：57（1分）五、證明（4小題，共30分）14. （10分）每步約1分，沒有P,T標識扣3分,沒有序號扣3分。證明過程：（1）PQP（2）QRP（3）QRT(2)E（4）PRT(1)（3）I（5）RP（6）PT（4）（5）I（7）SPP（8）ST(6)（7）I15. （10分）證明過程：證明：因為R和S都是非空集A上的等價關(guān)系，所

43、以R和S都有自反性，對稱性和傳遞性。（1分）（1）,則,所以,所以RS是自反的。（2分）（2），則，因為R和S是對稱的，所以（3分），從而,所以RS是對稱的。（3），則，因為R和S是傳遞的，所以，從而,所以RS是傳遞的。（3分）由上面的三點可得RS是A上的等價關(guān)系。（1分）16. （4分）證明過程：A(BC)A(BC)(AB)(AC)=(AB)(AC)=(AB)(AC)=(ABA)=(ABC)所以A(BC)(AB)(AC)。明顯，H是G的子集。5（6分）證明過程：證明：顯然，*運算封閉，且(a*b)*c=a*(b*c)=a+b+c-4,所以*滿足結(jié)合律。（3分）2是幺元，4-a是a的逆元。所以

44、是群。（3分）離散13一、選擇題（每題2分，共20分）BACDA CBDAC二、填空題（每題2分，共20分）1.s（R）=，,，2.a1,a2,a3,a4,a5或a4,a5,a6,a7,a8,=3.是一個群.4.連通且每個結(jié)點的度數(shù)為偶數(shù).5.自反的、對稱的和傳遞的 6. e*x=x*e=x 7. 主析取 8. x | (xA) (xB) 9. x z z y 10. 為n(n-1)/2三、判斷題（每題1分，共10分） 四、解答題（5小題，共30分）1（5分）圖G的正常著色(或簡稱為著色)是指對它的每一個結(jié)點指定一種顏色，使得沒有兩個相鄰的結(jié)點有同一種顏色。韋爾奇鮑威爾法(Welch Powell)對圖進行著色的方法：將圖G的結(jié)點按