離散數(shù)學(xué)題庫(kù)簡(jiǎn)答題

1、編題目答案號(hào)11設(shè)集合 A=a ， b， c， d 上的關(guān)系答 :R=<a , b > ,< b , a > ,< b, c > , < c ,01001010d > 用矩陣運(yùn)算求出 R 的傳遞閉包10100101t (R) 。， MR2 MRM R001M R0000000000000如下圖所示的賦權(quán)圖表示某七個(gè)城市 v1 , v2 , v7 及預(yù)先算出它們之間的一些直接通信線路造價(jià)，試給出一個(gè)設(shè)計(jì)方案，使得各城市之間能夠通信而且總造價(jià)最小。設(shè) <Z6,+6> 是一個(gè)群，這里+6 是模 6加法， Z 6=0， 1 ， 2 ， 3 ，

2、4 ， 5 ，試求出 <Z 6,+ 6>的所有子群。權(quán)數(shù)1， 4， 9， 16， 25， 36， 49，64 ， 81 ， 100構(gòu)造一棵最優(yōu)二叉樹(shù)。集合 X=<1,2>, <3,4>, <5,6>, ， R=<<x 1,y 1>,<x 2,y2 >>|x 1+y 2 =x2+y 1。1） 說(shuō)明R 是X 上的等價(jià)關(guān)系。（6分）2）求出 X 關(guān)于 R 的商集。（2分）t (R)=<a , a> , <a , b> , < a , c> , <a , d > , &l

3、t;b , a > , < b ,b > , < b , c . > , < b , d > ,答 : 用 Kruskal 算法求產(chǎn)生的最優(yōu)樹(shù)。算法略。結(jié)果如圖：樹(shù)權(quán) C(T)=23+1+4+9+3+17=57 即為總造價(jià)。答 : 子群有 <0,+6 >；<0,3,+6> ； <0,2,4,+6>； <Z 6,+ 6 >答 :答: 1）、1、自反性：x, yX , 由于 x yx y2、對(duì)稱(chēng)性：x1 , y1X ,x2 , y2X3、傳遞性：x1 , y1X ,x2 , y2Xx3 , y3即 x1y3x

4、3 y1由（ 1）（ 2）（ 3）知： R 是 X 上的先等價(jià)關(guān)系。2）、 X/R= 1 ,2 R設(shè)集合A=a ,b , c , d 上關(guān)系答 :R=< a, b > , < b , a > , < b , c > , <c , d >0100要求 1）、寫(xiě)出R 的關(guān)系矩陣和關(guān)10101、MR00；關(guān)系圖系圖。（ 4 分）2）、用矩陣運(yùn)算010000求出 R 的傳遞閉包。（ 4 分）10102、MR2MRM R010100000000t (R)=<a , a> , <a , b> , < a , c> , &l

5、t;a , d > , <b , a > , < b ,b > , < b , c . > , < b , d >利用主析取范式，判斷公式(PQ)QR(PQ)(QR)(PQ) Q R 的類(lèi)型。答 :(Q R)PQQRF(PQ)它無(wú)成真賦值，所以為矛盾式。在二叉樹(shù)中 :1) 求帶權(quán)為 2， 3， 5，答 : （ 1）由 Huffman方法 ,得最佳二叉樹(shù)為：7， 8的最優(yōu)二叉樹(shù) T 。（ 4分） 2)（ 2）最佳前綴碼為：000， 001， 01， 10， 11求 T 對(duì)應(yīng)的二元前綴碼。（4 分）下圖所示帶權(quán)圖中最優(yōu)投遞路線并答: 圖中奇數(shù)點(diǎn)

6、為 E、F， d(E)=3,d(F)=3,d(E,F)=28求出投遞路線長(zhǎng)度 （郵局在 D 點(diǎn)）。p=EGF 復(fù)制道路 EG 、 GF，得圖 G ，則 G 是歐拉圖。由 D 開(kāi)始找一條歐拉回路： DEGFGEBACBDCFD 。道路長(zhǎng)度為：35+8+20+20+8+40+30+50+19+6+12+10+23=281。設(shè)S=1, 2, 3, 4, 6, 8,12,24 ，“ ”為 S上答:(1)=<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,4><

7、;2,12>,<2,24>,<3,6>,<3,12>,<3,24>,<4,8>,<4,12>,<4,24>,<6,12>,<6,24>,<8,24>整除關(guān)系，問(wèn)： （ 1）偏序集covS=<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,8>,<4,12>,<6,12> ,<8,24>,<12,24>S ,的 Hass 圖如何？Hass

8、 圖為（2）偏序集 S , 的極小元、（ 2）極小元、最小元是1，極大元、最大元是24。最小元、極大元、最大元是什么?設(shè)解釋 R 如下： DR 是實(shí)數(shù)集，答 : 公式 A 涵義為：對(duì)任意的實(shí)數(shù)x,y,z ，如果 x<y則 (x-z) < (y-z)D 中特定元素 a=0，D 中特定A 的真值為：真（ T）。RR函數(shù) f ( x, y) xy ，特定謂詞 F ( x, y) : xy ， 問(wèn) 公 式Ax yz( F (x, y)的 涵F ( f ( x, z), f ( y, z)義如何？真值如何？給定 3個(gè)命題： P：北京比天津人答 : P， Q 是真命題， R 是假命題?？诙啵?

9、Q： 2 大于1； R： 15是素?cái)?shù) 。求 復(fù)合 命 題：(QR)( PR) 的真值。給定解釋I ： D=2 ， 3 ， L （ x,y ）yxL ( x, y)y(L(2, y)L(3, y)( L( 2,2) L(3,2) ( L(2,3)為 L(2,2)=L(3,3)=1,L(2,答 :0)(01)0003)=L(3,2)=0,求謂詞合式公式(1y xL( x, y)的真值。wffx( yP( x, y)答 :將zQ( z)化 為(R( x)與其等價(jià)的前束范式。簡(jiǎn)述關(guān)系的性質(zhì)有哪些？自反性，對(duì)稱(chēng)性，傳遞性，反自反性，反對(duì)稱(chēng)性假設(shè)英文字母， a， e， h， n， p，答 :解：傳輸它們的

10、最佳前綴碼如上圖所示，happy new year的編碼信息為：r， w ， y 出現(xiàn)的頻率分別為12% ，10 011 0101 0101 001 110 111 0100 001 111 011 0008%， 15% ， 7%， 6%， 10%， 5% ，附：最優(yōu)二叉樹(shù)求解過(guò)程如下：10% ，求傳輸它們的最佳前綴碼，并給出 happy new year的編碼信息。用 washall 方法求圖的可達(dá)矩陣，0011并判斷圖的連通性。1010答:A(G)00010100設(shè)有 a、 b、 c、 d、 e、 f 、 g 七個(gè)人，他們分別會(huì)講的語(yǔ)言如下：a：英， b ：漢、英， c：英、西班牙、俄，

11、d：日、漢， e：德、西班牙， f：法、日、俄， g：法、德，能否將這七個(gè)人的座位安排在圓桌旁，使得每個(gè)人均能與他旁邊的人交談？00110i1011i11：A2 ， 1=1 ， A00；2： A4 ， 2=1 ， A010010010011i3： A1 ， 3=A2 ， 3=A4，3=1 ， A1011000111111111i11114： Ak ， 4=1 ， k=1 ， 2， 3， 4， A11111111p 中的各元素全為1，所以G 是強(qiáng)連通圖，當(dāng)然是單向連通和弱連通。答 :用 a,b,c,d,e,f,g 7 個(gè)結(jié)點(diǎn)表示 7 個(gè)人，若兩人能交談可用一條無(wú)向邊連結(jié)，所得無(wú)向圖為此圖中的Ha

12、milton 回路即是圓桌安排座位的順序。Hamilton 回路為 a b d f g e c a 。用 Huffman 算法求出帶權(quán)為2， 答 :3， 5， 7， 8， 9 的最優(yōu)二叉樹(shù)T ，（ 1） 用 0000 傳輸 a、 0001 傳輸 b、 001 傳輸 c、 01 傳輸 f 、 10 傳輸 d、 11 傳輸并求 W（ T ）。若傳遞 a ， b， c，d ， e， f 的頻率分別為2% ，傳輸它們的最優(yōu)前綴碼為0000 ， 0001， 001 ， 01， 10， 11 。3% ， 5 %， 7% ，8% ，9%求傳輸它的最佳前綴碼。（構(gòu)造一個(gè)結(jié)點(diǎn)v 與邊數(shù)e 奇偶性相反的歐拉圖。答

13、 :設(shè)A=1 ，2，3，4 ，S=1，答:R=<1,1>,<2,2>,<2,3>,<3,2>,<3,3><4,4>2 ， 3 ， 4 ，為 A 的一個(gè)分劃，求由 S 導(dǎo)出的等價(jià)關(guān)系。設(shè) A x1 , x2 , x3 , x4 , x5 ， 偏 序答 : A 中最大元為x1 ，最小元不存在；集A, R的 Hass 圖為 x3 , x4 , x5 上界 x1 ,x3 ，上確界 x1；下界無(wú)，下確界無(wú)。求 A中最小元與最大元； x3 , x4 , x5 的上界和上確界，下界和下確界。用 Warshall 算法，對(duì)集合A=1 ，答

14、 :2，3，4，5上二元關(guān)系R=<1,1>,<1,2>,<2,4>,<3,5>,<4,2>求 t（ R）。i1時(shí)， MR1,1=1,A= M Ri2 時(shí)， M1,2=M4,2=11101000010A=000010101000000i3 時(shí)， A 的第三列全為0，故 A 不變i4 時(shí)， M1,4=M2,4=M4,4=11101001010A=00001i 5 時(shí)， M3,5=1，這時(shí)01010000001101001010A=000010101000000所以 t (R)=<1,1>, <1,2>,<1,

15、4>,<2,2>,<2,4>,<3,5>,<4,2>,<4,4>。將謂詞公式( x)(P( x) (yQ( y)( y) R( y)(x)P( x)( xP( x)( yQ( y)(y) R( y)( x) P( x)(y)(Q( y)( y)R( y)(y)Q( y)(y) R( y)(x)P( x)(yQ( y)(y)R( y)化為前束析取范式與前束合答:(x)P( x)(yQ( y)(z)R(z)取范式。(x)(y)(z)(P( x)Q( y)R( z)前束析取范式(x)(y)(z)(P( x)R( z)(Q( y) R(

16、 z)前束合取范式 ) 、畫(huà)一個(gè)有一條歐拉回路和一答 :條漢密爾頓回路的圖。 ) 、畫(huà)一個(gè)有一條歐拉回路，但沒(méi)有一條漢密爾頓回路的圖。 ) 、畫(huà)一個(gè)有一條歐拉回路，但有一條漢密爾頓回路的圖。求(QP)(PQ)的主合取范式。在下面關(guān)系中:Rx,yx y 2 0 x y 2 0判定關(guān)系的性質(zhì)。(QP)(PQ)(QP)(PQ)答:(QPQ)(PPQ)F(PQ)(PQ)(PQ)(PQ)答: R 自反任意實(shí)數(shù)x， x-x+2>0， x-x-2<0, 所以直線y=x 上的點(diǎn)在區(qū)域內(nèi)，即<x反；R 對(duì)稱(chēng)若 x, yRx y 2 0y x 2(x y 2)0有得y x 2(x y 2)即x

17、y 2 00所以 R 對(duì)稱(chēng)；因 R 自反且結(jié)點(diǎn)集非空，故R 非反自反；因 R 對(duì)稱(chēng)且結(jié)點(diǎn)集非空，并非全是孤立點(diǎn)，故R 不是反對(duì)稱(chēng)；xy20x 2 所以 1, 1R而 1,由y2得 x 2 yx04所以 R4 不是傳遞的。求圖的鄰接矩陣和可達(dá)矩陣。答 :00000000001011010100A(G) 10000， A2 (G)00000，001001000000000000000000010000A3 (G) 00000， A4(G) O5 5 。00000000000000010110234所以可達(dá)矩陣PAAAA100001010000000答 :已知某有向圖的鄰接矩陣如下：00101101

18、1021v10010A0011， A22101， A31031，v20011102111013212A1101100000101101v3v410003212試求： v3到 v1 的長(zhǎng)度為 4 的有向A44313，由 v3 到 v1 長(zhǎng)度為4 的有向路徑的條數(shù)為3 條。3153路徑的條數(shù)。1021已知某樹(shù)有2個(gè)2度結(jié)點(diǎn)、3個(gè)3答 : 設(shè)該樹(shù)有 t片樹(shù)葉，總結(jié)點(diǎn)數(shù)為d (v)223344t29度結(jié)點(diǎn)、 4 個(gè) 4 度結(jié)點(diǎn)，問(wèn)有幾個(gè)葉子點(diǎn)（無(wú)其它度數(shù)點(diǎn)）?？傔厰?shù)為e v1234t18t所以 ， 29+t=2·(8+t)即 t=13。 該樹(shù)有13 片樹(shù)葉。設(shè) R1和 R2是 A 上的任意二

19、元關(guān)答 : 若 R1 , R2 是自反的，則R1R2 也是自反的。因?yàn)橄担绻?R1和 R2是自反的，aA ,R1 , R2 自反，a, aR1 ,a, aR2 ，從而a,aR1 R2是否也是自反的，為什R1 R2 也是自反的。么？如果 R1和 R2是對(duì)稱(chēng)的，若 R1 , R2 是對(duì)稱(chēng)的，但R1R2 不一定是對(duì)稱(chēng)的。R1 R2 是對(duì)稱(chēng)的嗎？如： A= a, b, c ， R1 a, b,b, a，R2b,c,c,b ，的，但 R1R2a,c 不是對(duì)稱(chēng)的。如圖給出的賦權(quán)圖表示六個(gè)城市答 : 要設(shè)計(jì)一個(gè)方案使各城市間能夠通訊且總造價(jià)最小，即要求該圖連通、無(wú)回路a, b, c,d ,e, f及架起城

20、市間直接的子圖即最小生成樹(shù)，由避圈法或破圈法可得：其最小生成樹(shù)為：通訊線路的預(yù)測(cè)造價(jià)。試給出一個(gè)其樹(shù)權(quán)即最小造價(jià)為：1+2+3+5+7=18 。設(shè)計(jì)方案使得各城市間能夠通訊且總造價(jià)最小，并計(jì)算出最小總造價(jià)。設(shè) S = R - -1 （ R 為實(shí)數(shù)集），答 : 1）a, bS易證abababS ，即運(yùn)算 * 是封閉的。ababab 。說(shuō)明S,是否構(gòu)成群；2）a,b,cS而(ab) ca(b c) ，即 * 可結(jié)合。3）設(shè) S 關(guān)于 * 有幺元 e，則a S , e a a e a 。而 a e e a a e ea a ,e0 。4）aS 設(shè)有逆元 a 1。則 aa 1a 1ae ，即 aa 1

21、aa 10 ，a 11a ，即S 中任意元都有逆元，綜a構(gòu)成群。將公式答 :原式( PQ )R)(PR)(PQ)R(PR)(P Q) R） (PR)劃為只含有聯(lián)結(jié)詞， 的等價(jià)公式。( PQ )R(PR) 。設(shè)H ,和K ,都 是 群答 :HK ,是G ,的子群，HK ,不一定是G ,的G ,的子群，問(wèn)a, bHK , 則a, bH , a,bK , 由H ,和K ,都HK ,和HK ,是群，否是G,的子群并說(shuō)明理由。a b 1H 且 a b 1K ,a b 1H K ,H K ,的子群。如： G = 1 ， 5， 7， 11 ，：模 12乘，則G ,為群。且 H=1 ，H ,和 K ,皆為G,

22、的子群，但HKH K ,不是G ,的子群。因?yàn)?711HK ，即運(yùn)算不封設(shè)A2，3，4，9， 答 :R 2,2 , 2,4 , 2,10 , 2,12 , 3,12 , 4,4 ,ABB 2 ，4 ，7 ，10 ,12，從A 到關(guān)系圖為：2R 的關(guān)系矩陣為2B 的關(guān)系43R a , b a A , b B ,關(guān)系 R 不是 A 到 B 的函數(shù)，因?yàn)樵?， 4 的象不唯一（或元素9 無(wú)象）。7且 a 整除 b410，試給出R 的關(guān)系圖和關(guān)系矩912陣，并說(shuō)明此關(guān)系是否為函數(shù)？為什么？設(shè)S ,是半 群 ， OL 是左 零答 :xO L 仍是左零元。因?yàn)閥S ，由于 O L 是左零元，所以，O L

23、yO L元，對(duì)任xS , xOL 是否是左零元？為什么？某次會(huì)議有 20 人參加，其中每人至少有 10 個(gè)朋友，這 20 人擬圍一桌入席，用圖論知識(shí)說(shuō)明是否可能每人鄰做的都是朋友？（理由）通過(guò)主合取范式，求出使公式(PQ)R的值為 F的真值指派。S,為半群，所以* 可結(jié)合。所以， ( xOL )yx(OLy)xO L ，所以，xOL 仍是左零元。答 : 可能。將人用結(jié)點(diǎn)表示，當(dāng)兩人是朋友時(shí)相應(yīng)結(jié)點(diǎn)間連一條邊，則得一個(gè)無(wú)向G V , E ， 20 人圍一桌，使每人鄰做都是朋友，即要找一個(gè)過(guò)每個(gè)點(diǎn)一次且由題已知，u , v V ,deg(u)10 , deg(v) 10 ，deg(u) deg(v

24、理， G 中存在一條漢密爾頓回路。即所談情況可能。原式(PQ)R (PQ) R(P R) (Q答 :(PQR)(PQR)(PQR)(PM 100M 110M 010使公式(P Q)R 的值為 F 的真值指派為：P :1P :1P :0Q:0；Q : 1；Q:1。R :0R :0R :0設(shè) A a , b , c ， A上的關(guān)系答 : r () a, a ,a,b, b, c ,c, b, b,b , c, c ，a , a, a , b ,b, c ,c , b ，求出 r ( ) , s() 和 t() 。s() a, a,a,b,b,c,c, b,b, a ，2a, a,a,b,a, c,

25、b,b,c,c ，32a,a,a, b,a, c,a,b,b, c,c, b ，t ()2a, a,a, b, a, c, b,b, c, c ,b, c ,已 知 G 1，2 ，3，4 ，5 ，6，答 :G， 7既構(gòu)成群，又構(gòu)成循環(huán)群，其生成元為3， 5。因?yàn)椋? 的運(yùn)算表7 為 模7 乘法。試說(shuō)明1）由運(yùn)算表知，7 封閉；G， 7是否構(gòu)成群？是否2）7 可結(jié)合（可自證明）為循環(huán)群？若是，生成元是什3）1 為幺元；么？4） 111， 214 ，315 ，412， 513， 616 ，綜上所述，G， 7構(gòu)成群。由 313， 322， 336，344， 355， 361。所以， 3 為其5 也為

26、其生成元。故G， 7為循環(huán)群。用等值演算法求下面公式的主析取答 :原式范式，并求其成真賦值。 使其成真賦值為：P 0P 0P 1P 1P 0P 0Q0，Q0，Q1，Q0，Q0，Q1R 1R 0R 1R 1R 1R1集 合 A1,2,3,4 上的關(guān)系答 :R1,1,1,3,2,210100100, 3,3,3 , 1, 3,4,M R101R 的關(guān)系圖為4 , 3,4 , 410011，寫(xiě)出關(guān)系矩陣 M R ，畫(huà)出關(guān)系圖R 是自反、對(duì)稱(chēng)的。并討論 R 的性質(zhì)。一棵樹(shù) T 中，有 3 個(gè) 2 度結(jié)點(diǎn)，一答 : （ 1）設(shè)該樹(shù)樹(shù)葉數(shù)為t，則樹(shù) T 的結(jié)點(diǎn)數(shù)為31t ，又邊數(shù)=結(jié)點(diǎn)數(shù) 個(gè) 3 度結(jié)點(diǎn)，

27、其余結(jié)點(diǎn)都是樹(shù)葉。deg(vi )邊數(shù) 2倍 ，3213 t 12(3t 1 1)（ 1） T 中有幾個(gè)結(jié)點(diǎn)；（ 2）畫(huà)出即9t62t ， t3， T中 7個(gè)結(jié)點(diǎn)。具有上述度數(shù)的所有非同構(gòu)的無(wú)向（ 2）具有3 個(gè)兩度結(jié)點(diǎn)，一個(gè)3 度結(jié)點(diǎn)， 3 片樹(shù)葉的樹(shù)（非同構(gòu)的）共有圖。設(shè) A=1,2,10 。下列哪個(gè)是A答 : （ 1）和（ 2）都不是 A 的劃分。的劃分？若是劃分，則它們誘導(dǎo)的（ 3）是 A 的劃分。其誘導(dǎo)的等價(jià)關(guān)系是等價(jià)關(guān)系是什么？I A<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,（ 1） B=1,3,6,2,8,10,<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>。4,5,7;（ 2