本部_離散數(shù)學(xué)II_試卷_a_答案

1、 計(jì)算機(jī)學(xué) 院、系2005 /2006 學(xué)年（ 1 ）學(xué)期期末考試試卷 離散數(shù)學(xué)II 試卷（A 卷）專業(yè) 年級(jí) 班級(jí) 姓名 學(xué)號(hào) 題號(hào)一二三四五六七八九十總分得分一、單選題 (在每小題的四個(gè)備選答案中，選出一個(gè)最正確的答案，并將答案的序號(hào)填在題干的括號(hào)內(nèi)。每小題2分，共24分)1、由r棵樹組成的森林的頂點(diǎn)數(shù)n與邊數(shù)m有下列關(guān)系（ B ）。An=m-rBn=m+rCn=m-1Dm+n+r=02、若無向圖G中不含孤立點(diǎn)，且存在一條經(jīng)過所有邊的閉路徑，則（B）。AG必為哈密頓圖BG必為歐拉圖CG必為不連通圖DG必為簡(jiǎn)單圖3、下圖是（ C ）。 A強(qiáng)連通B單側(cè)連通C弱連通D不連通4、以下是簡(jiǎn)單圖的度序

2、列的是（ C ）。A(5,4,3,2,2,2,1)B(7,6,5,4,4,3,1)C(6,43,3,3,2,1)D(6,6,4,3,2,2,1)5、下列無向圖中，不是哈密頓圖的是（ B ）。6、滿足下列條件（ A ）的無向圖不一定是樹。A邊數(shù)=頂點(diǎn)數(shù)-1B任意一對(duì)結(jié)點(diǎn)間有且僅有一條通路C連通且無回路D無回路，但添加任何一條邊后必產(chǎn)生唯一回路7、設(shè)為一代數(shù)系統(tǒng)，S=e,a,b。*運(yùn)算定義如下。則（ D ）為其子代數(shù)。*eabebbeaebabbeeABCD8、以下代數(shù)系統(tǒng)中，群是（ D ）。*abcd*abcdaabcdaabcdbbeacbbbbbccdbaccbadddaebddbcaAB*

3、abcd*abcdaabcdabadcbbadcbabcdccdcacdcabddcbadcdbaCD9、設(shè)為一代數(shù)系統(tǒng)，aS，則（ A ）。A 若a存在逆元，則其逆元未必唯一B 若中存在幺元，則幺元未必唯一C 若中既有幺元又有零元，則幺元、零元必不相等D 若a既有左逆元，又有右逆元，則左、右逆元必相等10、為兩個(gè)代數(shù)系統(tǒng)，且存在S到S1的同態(tài)映射h，則（ B ）。A 若中存在幺元，則也存在幺元B 若中存在幺元，則未必存在幺元C 若中每個(gè)元素存在逆元，則中每個(gè)元素存在逆元D 若中滿足結(jié)合律，則中*也滿足結(jié)合律11、下列代數(shù)系統(tǒng)中，不構(gòu)成群的是（ C ）A S=1,3，*是模4的乘法BS是有理數(shù)

4、集，*是普通加法CS是實(shí)數(shù)集，*是普通乘法DS是整數(shù)集，*是普通加法12、設(shè)是群，為其子群，則（ B ）。AaH，a在H中的逆元與a在G中的逆元未必相等BaH，a在H中的逆元與a在G中的逆元一定相等C中的幺元與中的幺元未必相等D中必存在零元，且與中的零元相等二、填空題（除特別說明外，每空2分，共33分）1、設(shè)簡(jiǎn)單圖G共有10個(gè)頂點(diǎn)，其中，8個(gè)頂點(diǎn)的度數(shù)為3，其余4個(gè)頂點(diǎn)的度數(shù)都小于3，則G至多有 14 條邊。2m83+222、樹T有5個(gè)2度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余都是樹葉，則T的樹葉有 12 個(gè)。m=n-1=5+4+3+x-1, 2m=52+43+34+x3、為了從（n,m）連通

5、圖中得到一棵最小生成樹，必須刪除G的 m-(n-1) 條邊。4、20階完全圖的關(guān)聯(lián)矩陣共有 380 個(gè)1，30階有向完全圖的鄰接矩陣共有 900 個(gè)1。20192=190，1902=380；3030=9005、下圖的一條歐拉閉路徑為 abdfecdebca 。 6、設(shè)是一代數(shù)系統(tǒng)，R為S之上的一個(gè)二元關(guān)系。如果R是等價(jià)關(guān)系且對(duì)于p,q,r,tS有pRq且rRt蘊(yùn)涵(p*r)R(q*t)，則稱R是上的同余關(guān)系。7、設(shè)為群，群的幺元為e。對(duì)任意aG，則稱滿足ar=e的最小正整數(shù)r 為元素a的階。群中任意元素的階 |G|。8、(2分)設(shè)是群，對(duì)a,bG，填寫以下計(jì)算過程中每一步的理由(a*b)*(b

6、-1*a-1) =a*(b*b-1)*(a-1) *滿足結(jié)合律 =e逆元定義、幺元定義9、(5分)設(shè)是環(huán)（是阿貝爾群，是半群，對(duì)+滿足分配律），0是環(huán)的加法幺元、乘法零元。對(duì)a,bR，-a表示a的加法逆元。填寫以下證明過程每步的理由。(-a)b=(-a)b+(ab+(-(ab) 逆元定義ab+(-(ab)=0, 幺元定義(-a)b+0=(-a)b =(-a)b+ab)+(-(ab) +滿足結(jié)合律 =(-a)+a)b+(-(ab) 對(duì)滿足分配律 =0b+(-(ab) (-a)+a0 =-(ab) 0b=0,0+(-(ab)=(-(ab)10、設(shè)為群，為其子群，利用可定義G上的一個(gè)右陪集關(guān)系（等價(jià)

7、關(guān)系）=|ab當(dāng)且僅當(dāng)a、b在H的同一個(gè)左（右）陪集中/a,bG,a*b-1H。a關(guān)于H的右陪集Ha= h*a|hH，其性質(zhì)為|Ha| |H|。三、計(jì)算題（共35分）1、（11分）對(duì)下列有向圖 （1）（2分）該圖是否有關(guān)聯(lián)矩陣表示？如果有，寫出關(guān)聯(lián)矩陣；如果沒有，說明為什么沒有？回答1：沒有。因?yàn)殛P(guān)聯(lián)矩陣無法表示邊的方向，無法表示環(huán)?；卮?（其他課本有）：有，用1和-1表示邊的方向。（2）（4分）寫出該圖的鄰接矩陣；寫出（不需計(jì)算）路徑矩陣和可達(dá)矩陣；A= 1 1 1 0B= 1 1 1 1P=B 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 1（

8、3）（3分）求出v1到v4的長(zhǎng)度為3的擬路徑條數(shù)，要求寫出計(jì)算過程；計(jì)算A、A2、A3，取A31行4列元素A2=1 1 2 2A3=1 3 3 3 0 1 0 00 0 0 1 0 1 1 1 0 1 1 2 0 0 0 1 0 1 0 0v1到v4的長(zhǎng)度為3的擬路徑條數(shù)為3條（4）（2分）如何通過鄰接矩陣計(jì)算判斷有向圖是否強(qiáng)連通？簡(jiǎn)單闡述判斷過程。通過鄰接矩陣計(jì)算出可達(dá)矩陣，判斷可達(dá)矩陣是否全1。2、（每小題3分，共6分）按要求畫圖：（1）畫出5個(gè)結(jié)點(diǎn)的所有不同構(gòu)的樹；3棵，度序列分別為(4,1,1,1,1)(3,2,1,1,1)(2,2,2,1,1)。每棵1分；多了同構(gòu)的樹扣1分；多了不是

9、樹的圖扣1分。（2）畫出算術(shù)表達(dá)式a*3+5/(b-c)+7的二元樹表示。3分。運(yùn)算符做分支結(jié)點(diǎn)、操作數(shù)做葉子結(jié)點(diǎn)、有序樹（左右兒子有序）1分；運(yùn)算符計(jì)算次序正確1分；樹完整1分。3、（8分）設(shè)S=a,b,c,d,e，S上的運(yùn)算*運(yùn)算表如下：*abcdeaaaaaabaecbdcacbcddabcdeeadded（1）（1分）*是否有零元？a（2）（1分）*是否有幺元？d（3）（5分）每個(gè)元素是否有逆元？寫出各個(gè)元素的所有逆元。a無逆元，b逆元為e，c逆元為e，d逆元為d，e逆元為b,c,e（4）（1分）*是否滿足交換律？是4、（10分）S= a,b,c,d，構(gòu)造群，并使c為幺元。（1） （2分）完成*的運(yùn)算表； *abcdabdacbdcbacabcddcadb（2） （4分）寫出各個(gè)元素的逆元和階；a、d互為逆元,c逆元是自己，b逆元是自己。a、d的階是4，b的階是2（3） （2分）找出的所有子群；3個(gè)c,c,b,c,a,b,d（4） （2分）該群是否是循環(huán)群？若不是，說明理由；若是，找出所有的生成元。是，生成元可以是a或d四、證明題（8分）設(shè)是一群，是其子群。求證：若AB=G，則必有A=G或B=G。證明：（反證法