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

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

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ù)=頂點數(shù)-1B任意一對結點間有且僅有一條通路C連通且無回路D無回路，但添加任何一條邊后必產(chǎn)生唯一回路7、設為一代數(shù)系統(tǒng)，S=e,a,b。*運算定義如下。則（ D ）為其子代數(shù)。*eabebbeaebabbeeABCD8、以下代數(shù)系統(tǒng)中，群是（ D ）。*abcd*abcdaabcdaabcdbbeacbbbbbccdbaccbadddaebddbcaAB*

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

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

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

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

7、關系）=|ab當且僅當a、b在H的同一個左（右）陪集中/a,bG,a*b-1H。a關于H的右陪集Ha= h*a|hH，其性質為|Ha| |H|。三、計算題（共35分）1、（11分）對下列有向圖 （1）（2分）該圖是否有關聯(lián)矩陣表示？如果有，寫出關聯(lián)矩陣；如果沒有，說明為什么沒有？回答1：沒有。因為關聯(lián)矩陣無法表示邊的方向，無法表示環(huán)。回答2（其他課本有）：有，用1和-1表示邊的方向。（2）（4分）寫出該圖的鄰接矩陣；寫出（不需計算）路徑矩陣和可達矩陣；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的長度為3的擬路徑條數(shù)，要求寫出計算過程；計算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的長度為3的擬路徑條數(shù)為3條（4）（2分）如何通過鄰接矩陣計算判斷有向圖是否強連通？簡單闡述判斷過程。通過鄰接矩陣計算出可達矩陣，判斷可達矩陣是否全1。2、（每小題3分，共6分）按要求畫圖：（1）畫出5個結點的所有不同構的樹；3棵，度序列分別為(4,1,1,1,1)(3,2,1,1,1)(2,2,2,1,1)。每棵1分；多了同構的樹扣1分；多了不是

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