最新離散數(shù)學(xué)試卷及答案(13)

1、精品文檔填空10% （每小題2分）1、Z x|x Z x 0 ,*表示求兩數(shù)的最小公倍數(shù)的運(yùn)算（Z表示整數(shù)集合），對于*運(yùn)算的幺元是 2、代數(shù)系統(tǒng)A,*中，冏1 ,如果酢口 分另J為A,*的幺元和零元,則e和的關(guān)系為3、設(shè)G,*是一個群，G,*是阿貝爾群的充要條件是eS4精品文檔4、圖的完全關(guān)聯(lián)矩陣為5、一個圖是平面圖的充要條件是選才? 10% （每小題2分）1、卜面各集合都是N的子集，（）集合在普通加法運(yùn)算下是封閉的。A、x | x的哥可以被16整除;B、x | x與5互質(zhì);C、x | x是30的因子;D、x | x是30的倍數(shù)。2、設(shè) Gi0,1,2,，G20,1,*,其中 表示模3加法，

2、*表示模2乘法，則積代數(shù)GiG2的幺元是（A、<0,0> B、<0,1>C、<1,0>D、<1,1> 。3、設(shè)集合S=1,2,3,6 , V 為整除關(guān)系，則代數(shù)系統(tǒng) S , 是（A、域；B、格，但不是布爾代數(shù)；C、布爾代數(shù)；D、不是代數(shù)系統(tǒng)。4、設(shè)n階圖G有m條邊，每個結(jié)點(diǎn)度數(shù)不是 k就是k+1 ,若G中有Nk個k度結(jié)點(diǎn),則 Nk=(A、n k; B、n(k+1); C、n(k+1)-m ; D、n(k+1)-2m 。5、一棵樹有7片樹葉，3個3度結(jié)點(diǎn)，其余全是 4度結(jié)點(diǎn),則該樹有（）個4度結(jié)點(diǎn)。A、1; B、2; C、3; D、4。三、判斷10

3、% （每小題2分）1、（）設(shè)S=1,2,則S在普通加法和乘法運(yùn)算下都不封閉。2、（）在布爾格A, w中，對a中任意原子a,和另一非零元b,在a b或a b中有且僅有一個成立。3、（）設(shè)S x|x Z x 0 N , +, 為普通加法和乘法，則 S, +, 是域。4、（） 一條回路和任何一棵生成樹至少有一條公共邊。5、（）沒T是一棵m叉樹，它有t片樹葉，i個分枝點(diǎn)，則（m-1）i = t-1 。四、證明38%1、（8分）對代數(shù)系統(tǒng)A,* , *是A上二元運(yùn)算，e為A中幺元，如果*是可結(jié)合的且每個元素 都有右逆元，則（1） A,*中的每個元素在右逆元必定也是左逆元。（2）每個元素的逆元是唯一的。2

4、、（12分）設(shè) A , 是一個布爾代數(shù)，如果在A上定義二元運(yùn)算，為ab （a b） （a b）,則 a,是一阿貝爾群。3、（10分）證明任一環(huán)的同態(tài)象也是一環(huán)。4、（8分）若G V,E （V v, |E e）是每一個面至少由k（k3）條邊圍成的連通平面 圖，則 e k（v 2）。k 2五、應(yīng)用32%1、 （8分）某年級共有9門選修課程，期末考試前必須提前將這 9門課程考完，每人每天 只在下午考一門課，若以課程表示結(jié)點(diǎn)，有一人同時選兩門課程，則這兩點(diǎn)間有邊（其 圖如右），問至少需幾天？2、用washall方法求圖的可達(dá)矩陣，并判斷圖的連通性。(8分)3、設(shè)有a、b、c、d、e、f、g七個人，他們

5、分別會講的語言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個人的 座位安排在圓桌旁，使得每個人均能與他旁邊的人交談？ （8分）4、用Huffman算法求出帶權(quán)為 2, 3, 5, 7, 8, 9的最優(yōu)二叉樹T,并求 W （T）。若傳遞a , b, c, d , e, f的頻率分別為 2%, 3% , 5 %, 7% , 8% , 9%求傳輸它 的最佳前綴碼。（8分）1、1,不存在；2、e填空10% （每小題2分）；3、a,b G 有(a* b)* (a * b) (a*a)*(b*b)；eie2e3e4e5V111100V2-

6、10001V30-101-1V400-1-105、它不包含與K3, 3或K5在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。選才i 10% （每小題2分）題目12345答案A , DBCDA三、判斷10%題目12345答案NYYNN四、五、證明38%1、(8分)證明：(1)設(shè)a,b,c A, b是a的右逆元，c是b的右逆元，由于 b*(a*b) b*e e b * c b*(a*b)*c (b*a)*(b*c) (b*a)*e b * a所以b是a的左逆元。(2)設(shè)元素a有兩個逆元b、c,那么b b * e b*(a*c) (b*a)*c e* c ca的逆元是唯一的。2、(12分)證明：乘, 在A上封閉， 運(yùn)算在A

7、上也封閉。群a,b,c A (abp c (a b) (a b)c(a b) (a b) c) (a b) (a b) c)(abc)(ab(abc)(ab(abc)(ab同理可得：a(b+c)c) (a b) (a b) c)c)(a b) (a b)c)c)(ab c) (a b c)(a b c) (a b c) (ab c)(ab c)(aib)ic a(bc)即滿足結(jié)合性。幺a A, ai0 0a (0 a) (0 a)0 (1 a) 0 a a故全下界0是A中關(guān)于運(yùn)算的幺元。逆aA, (aa) (a a) (a a) 0 0 0即A中的每一個元素以其自身為逆元。交ab (a b)

8、(a b)(b a) (b a)ba即運(yùn)算具有可交換性。所以A, +是Abel群。3、(10分)證明：設(shè) A, ,? 是一環(huán)，且f(A),是關(guān)于同態(tài)映射f的同態(tài)象。由 A, 是Abel群，易證 f(A),也是Abel群。A,? 是半群，易證 f(A),也是半群。現(xiàn)只需證： 對 是可分配的。bi,b2, b3f(A),則必有相應(yīng)的ai,a2,a3使得：f(ai) bi ,i 1,2,3 于是bi (b2 b3) f (ai) (f(a2) f。) f(ai) (f(a2 a3) f(ai(a2a3)f(aia?)(aia3)f(aia?) f(aia3)(f(ai) f(a2)(f(ai)f(a

9、3)(bib2)(bi b3)同理可證(b2 b3)bi (b2bi) (b3bi)因此 f(A),也是環(huán)。5、(8分)證明：設(shè)G有r個面,deg(h)i i2e,而 deg(rjk (i i r )2e kr 即 r2e k2,故v2re -kk(v 2)k 2六、應(yīng)用32%I、(8 分)解：(G)即為最少考試天數(shù)。用 Welch-Powell 方法對 G 著色：v9 v3v7v1v2 v4 v5v8v6第一種顏色的點(diǎn)v9 v1v4 v6 ,剩余點(diǎn)v3 v7 v2 v5v8第二種顏色的點(diǎn) V3V7V5 ,剩余點(diǎn)v2V8第三種顏色的點(diǎn) V2V8所以（G尸3任v2V3V9構(gòu)成一圈，所以（G）3故

10、（G）=3所以三天下午即可考完全部九門課程。1 11 00 12、(8 分)0 0幺10解：A(G)0 00 10 00 0 1110 11i 1: A2 , 1=1 , A;0 0 0 10 10 0i 3: A1 , 3=A2 , 3=A4 , 3=1 , Ai 4: Ak , 4=1 , k=1 , 2, 3, 4, A0 0 1110 11i 2: A4 , 2=1 , A0 0 0 111110 0 1110 110 0 0 111111111111111111111通和p中的各元素全為1,所以G是強(qiáng)連通圖，當(dāng)然是單向連 弱連通。3、（8 分）解：用a,b,c,d,e,f,g 7個結(jié)點(diǎn)表示7個人，若兩人能交談可用一 向邊連結(jié)，所得無向圖為條無此圖中的Hamilton回路即是圓桌安排座位的順序。Hamil