離散數(shù)學試卷及答案.doc

一、 填空 10% （每小題 2分）1、，*表示求兩數(shù)的最小公倍數(shù)的運算（Z表示整數(shù)集合），對于*運算的幺元是 ，零元是 。2、代數(shù)系統(tǒng)中，|A|1，如果分別為的幺元和零元，則的關(guān)系為 。3、設(shè)是一個群，是阿貝爾群的充要條件是 。4、圖的完全關(guān)聯(lián)矩陣為 。5、一個圖是平面圖的充要條件是 。二、 選擇 10% （每小題 2分）1、 下面各集合都是N的子集，（ ）集合在普通加法運算下是封閉的。A、x | x 的冪可以被16整除； B、x | x 與5互質(zhì)；C、x | x是30的因子； D、x | x是30的倍數(shù)。2、 設(shè)，其中表示模3加法，*表示模2乘法，則積代數(shù)的幺元是（ ）。A、； B、； C、； D、 。3、 設(shè)集合S=1,2,3,6，“”為整除關(guān)系，則代數(shù)系統(tǒng)是（ ）。A、域； B、格，但不是布爾代數(shù)； C、布爾代數(shù)； D、不是代數(shù)系統(tǒng)。4、 設(shè)n階圖G有m條邊，每個結(jié)點度數(shù)不是k就是k+1，若G中有Nk個k度結(jié)點，則Nk=（ ）。A、nk； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。5、 一棵樹有7片樹葉，3個3度結(jié)點，其余全是4度結(jié)點，則該樹有（ ）個4度結(jié)點。A、1； B、2； C、3； D、4 。三、判斷10% （每小題 2分）1、（ ）設(shè)S=1,2，則S在普通加法和乘法運算下都不封閉。2、（ ）在布爾格中，對A中任意原子a，和另一非零元b，在或中有且僅有一個成立。3、（ ）設(shè)，+,為普通加法和乘法，則是域。4、（ ）一條回路和任何一棵生成樹至少有一條公共邊。5、（ ）沒T是一棵m叉樹，它有t片樹葉，i個分枝點，則(m-1)i = t-1。四、證明 38%1、（8分）對代數(shù)系統(tǒng)，*是A上二元運算，e為A中幺元，如果*是可結(jié)合的且每個元素都有右逆元，則（1）中的每個元素在右逆元必定也是左逆元。（2）每個元素的逆元是唯一的。2、（12分）設(shè)是一個布爾代數(shù)，如果在A上定義二元運算，為，則是一阿貝爾群。3、（10分）證明任一環(huán)的同態(tài)象也是一環(huán)。4、（8分）若是每一個面至少由k(k3)條邊圍成的連通平面圖，則。五、應用 32%1、 （8分）某年級共有9門選修課程，期末考試前必須提前將這9門課程考完，每人每天只在下午考一門課，若以課程表示結(jié)點，有一人同時選兩門課程，則這兩點間有邊（其圖如右），問至少需幾天？2、 用washall方法求圖的可達矩陣，并判斷圖的連通性。（8分）3、 設(shè)有a、b、c、d、e、f、g七個人，他們分別會講的語言如下：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分）一、 填空 10%（每小題2分）1、1， 不存在；2、；3、有；4、11100-100010-101-100-1-105、它不包含與K3, 3或K5在2度結(jié)點內(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有兩個逆元b、c，那么a的逆元是唯一的。2、（12分）證明：乘 運算在A上也封閉。群 即滿足結(jié)合性。幺,故全下界0是A中關(guān)于運算的幺元。逆,即A中的每一個元素以其自身為逆元。交即運算具有可交換性。所以是Abel群。3、(10分) 證明:設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。由是Abel群，易證也是Abel群。是半群，易證也是半群?，F(xiàn)只需證：對是可分配的。 于是同理可證因此也是環(huán)。5、（8分）證明：設(shè)G有r個面， 。五、 應用32%1、（8分）解：即為最少考試天數(shù)。用Welch-Powell方法對G著色：第一種顏色的點 ，剩余點第二種顏色的點 ，剩余點第三種顏色的點 所以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是強連通圖，當然是單向連通和弱連通。3、（8分）解：用a,b,c,d,e,f,g 7個結(jié)點表示7個人，若兩人能交談可用一條無向邊連結(jié)，所得無向圖為此圖中的Hamilton回路即是圓桌安排座位的順序。Hamilton回路為a b