離散數(shù)學(xué)試卷及答案(共7頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、 填空 10% （每小題 2分）1、，*表示求兩數(shù)的最小公倍數(shù)的運(yùn)算（Z表示整數(shù)集合），對(duì)于*運(yùn)算的幺元是 ，零元是 。2、代數(shù)系統(tǒng)<A,*>中，|A|>1，如果分別為<A,*>的幺元和零元，則的關(guān)系為 。3、設(shè)<G,*>是一個(gè)群，<G,*>是阿貝爾群的充要條件是 。4、圖的完全關(guān)聯(lián)矩陣為 。5、一個(gè)圖是平面圖的充要條件是 。二、 選擇 10% （每小題 2分）1、 下面各集合都是N的子集，（ ）集合在普通加法運(yùn)算下是封閉的。A、x | x 的冪可以被16整除； B、x | x 與5互質(zhì)；C、x | x是30的

2、因子； D、x | x是30的倍數(shù)。2、 設(shè)，其中表示模3加法，*表示模2乘法，則積代數(shù)的幺元是（ ）。A、<0,0>； B、<0,1>； C、<1,0>； D、<1,1> 。3、 設(shè)集合S=1,2,3,6，“”為整除關(guān)系，則代數(shù)系統(tǒng)< S , >是（ ）。A、域； B、格，但不是布爾代數(shù)； C、布爾代數(shù)； D、不是代數(shù)系統(tǒng)。4、 設(shè)n階圖G有m條邊，每個(gè)結(jié)點(diǎn)度數(shù)不是k就是k+1，若G中有Nk個(gè)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個(gè)3度結(jié)點(diǎn)，其余全是4度結(jié)點(diǎn)，則該樹有（ ）個(gè)4度結(jié)點(diǎn)。A、1； B、2； C、3； D、4 。三、判斷10% （每小題 2分）1、（ ）設(shè)S=1,2，則S在普通加法和乘法運(yùn)算下都不封閉。2、（ ）在布爾格<A,>中，對(duì)A中任意原子a，和另一非零元b，在或中有且僅有一個(gè)成立。3、（ ）設(shè)，+,·為普通加法和乘法，則<S，+，·>是域。4、（ ）一條回路和任何一棵生成樹至少有一條公共邊。5、（ ）沒T是一棵m叉樹，它有t片樹葉，i個(gè)分枝點(diǎn)，則(m-1)i = t-1。四、證明 38%1、（8分）對(duì)代數(shù)系統(tǒng)<A,*>，*是A上二元運(yùn)算，e

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

5、的連通性。（8分）3、 設(shè)有a、b、c、d、e、f、g七個(gè)人，他們分別會(huì)講的語言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個(gè)人的座位安排在圓桌旁，使得每個(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分）一、 填空 10%（每小題2分）1、1， 不存在；2、；3、有；4、11100-100010-101-100-1-105、它不

6、包含與K3, 3或K5在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。二、 選擇 10%（每小題 2分）題目12345答案A，DBCDA三、 判斷 10%題目12345答案YYNNN四、 證明 38%1、（8分）證明：（1）設(shè)，b是a的右逆元，c是b的右逆元，由于，所以b是a的左逆元。（2）設(shè)元素a有兩個(gè)逆元b、c，那么a的逆元是唯一的。2、（12分）證明：乘 運(yùn)算在A上也封閉。群 即滿足結(jié)合性。幺 ,故全下界0是A中關(guān)于運(yùn)算的幺元。逆 ,即A中的每一個(gè)元素以其自身為逆元。交 即運(yùn)算具有可交換性。所以<A, >是Abel群。3、(10分) 證明:設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。由是Abel群，易證也

7、是Abel群。是半群，易證也是半群?，F(xiàn)只需證：對(duì)是可分配的。 于是同理可證因此也是環(huán)。5、（8分）證明：設(shè)G有r個(gè)面， 。五、 應(yīng)用32%1、（8分）解：即為最少考試天數(shù)。用Welch-Powell方法對(duì)G著色：第一種顏色的點(diǎn) ，剩余點(diǎn)第二種顏色的點(diǎn) ，剩余點(diǎn)第三種顏色的點(diǎn) 所以3任構(gòu)成一圈，所以3故=3所以三天下午即可考完全部九門課程。2、（8分）解：1：A2，1=1，； 2： A4，2=1，3： A1，3=A2，3=A4，3=1，4： Ak，4=1，k=1，2，3，4，p中的各元素全為1，所以G是強(qiáng)連通圖，當(dāng)然是單向連通和弱連通。3、（8分）解：用a,b,c,d,e,f,g 7個(gè)結(jié)點(diǎn)表示7個(gè)人，若兩人能交談可用一條無向邊連結(jié)，所得無向圖為此圖中的Hamilton回路即是圓桌安排座位的順序。Hamilton回路為a