1、院/系 年級 專業 姓名 學號 答 題 勿 超 裝 訂 線-裝-訂-線-安徽大學20 09 20 10 學年第 2 學期 離散數學（下） 考試試卷（A卷）（閉卷 時間120分鐘）題 號一二三四五總分得 分閱卷人得分一、單項選擇題（每小題2分，共20分）1. 設I為整數集，下列系統中不是代數系統的有( )。A.<I, ¸>B.<I, +> C.<I, ´>D.都不是。2. 下面的代數系統(G,*)中，( )不是群。A. G為整數集合，*為加法； B. G為偶數集合，*為加法；C. G為有理數集合，*為加法；D. G為有理數集合，*為乘法。3

2、. M2(R)=按矩陣的加法和乘法構成R上的二階方陣環,這個方陣環是( )A.有幺元的交換環B.無幺元的非交換環C.無幺元的交換環D.有幺元的非交換環4. 下列說法不正確的是（ ） A兩個域的直接乘積是域B. 有限整環是域 C次對稱群的階是D. 域只有平凡理想5. 下列整數集對于整除關系都構成偏序集，而能構成格的是（  ）Al，2，3，4，6  B1，2，3，6，12 C2，3，6  Dl，2，36記N是自然數集，是小于等于關系，則<N, >是( ).A. 有界格 B. 有補格 C. 分配格 D. 有補分配格7. 在布爾代數上定義的n元布爾表達式所對應

3、的不同主析取范式總個數為（ ） AB. C. D. 8. 無向圖的關聯矩陣中“關聯”指的是( )。 A. 結點與結點的關聯 B.邊與邊的關聯 C. 邊與結點的關聯 D.都不是9. 設G是具有n個結點m條邊，k個面的連通平面圖，其中，則有（ ）成立。ABCD10. 設G是由5個結點組成的無向完全圖，則從G中刪去（ ）條邊可以得到樹。 A4 B5 C6 D10得分二、判斷題（對的打，錯的打×，每小題2分，共10分）1. 若群G的每個元素都滿足方程x2=e，其中e為幺元，則G為交換群。 （ ）2. 若群G的階為n，d為n的一個因子，則G一定有階為d的子群。 （ ）3. 如果環R滿足左消去律

4、，則R必定沒有右零因子。 （ ）4. 設G=<V,E>是無向簡單圖,G的極小支配集都是G的極大獨立集。 （ ）5. 設是有10個結點的無向圖，對于中任意兩個不鄰接的結點u和v,均有，則是哈密爾頓圖。 （ ）得分三、填空題（每小空2分，共20分）1. 設G是由12個元素構成的循環群，a是G的一個生成元素，則G有_ _個非平凡子群。G的生成元素集合是_ _。2. 設是群的子群，則的充要條件是_。3. 設a,b分別是群G的3階和5階元，且ab=ba，則ab的階為_ _。4. 整數環有_ _個可逆元。5. 如果一個格中存在全上界和全下界，則這個格是_。6所有模格組成的集合_（填或）所有分配

5、格組成的集合。7設是連通圖，則的生成樹的個數至多為_。8含5個結點、3條邊的不同構的無向簡單圖個數為 _ 。9設無向圖有12條邊，有6個3度結點，其余結點度數均小于3，則中結點數至少為 _ _ 。得分 答 題 勿 超 裝 訂 線-裝-訂-線-四、解答題（每小題10分，共30分）1. 給出一個含有四個四元置換的集合,其中, ,在合成運算下組成的群，試求的所有正規子群，并且求關于每個正規子群的商群及各商群中的運算表。2. 設為一布爾代數，試化簡布爾表達式。3. 給定彼得森(Petersen)圖如右圖所示。試求圖的支配數、點覆蓋數、邊覆蓋數、獨立數、匹配數、點連通度、邊連通度、點色數、邊色數，以及鄰

6、接矩陣（結點與自身鄰接，結點次序按字母順序）。 答 題 勿 超 裝 訂 線-裝-訂-線-得分五、證明題（每小題10分，共20分）1. 設G是群，a,b是G中任意兩個元素，則ab的階與ba的階相同。 2. 設是一棵樹且，證明：中至少有個結點的度為1。 安徽大學20 09 20 10 學年第 2 學期離散數學（下）考試試題（A卷）參考答案及評分標準一、單選題（每小題2分，共20分）1. A；2. D；3. B；4. A；5. B；6. C；7. C；8. C；9. A；10. C。二、判斷題（每小題2分，共10分。對的打，錯的打×）1. ；2. ×；3. ；4. ×；

7、5. ×。三、填空題（每小空2分，共20分）1. 4; a,a3,a5,a7,a11; 2. （或）; 3. 15; 4. 2; 5. 有界格; 6. ; 7. ; 8. 4; 9. 9.四、計算題（每小題10分，共30分）1. 解：的正規子群有、。 （5分）的商群為，其中*運算表為： （6分） * 的商群為，其中*運算表為： （7分） * 的商群為，其中*運算表為： （8分） * 的商群為，其中*運算表為： （9分） * 的商群為，其中*運算表為： （10分） * 2. 解：（共10分） (2分) (6分) (10分)3. 解: （每空1分，共10分）365453334鄰接矩陣:

8、最小支配集：b,f,e,最小點覆蓋：b,d,e,f,g,h,最小邊覆蓋：(a,b),(c,d),(e,j),(f,h),(g,i)，最大獨立集：b,e,h,i，最大匹配：(a,b),(c,d),(e,j),(f,h),(g,i)，最小點割：b,f,e,最小割集：(a,b),(a,f),(a,e)，點正常著色：b,e,h,i,a,c,j,d,f,g.邊正常著色：(a,b),(c,d),(e,j),(f,h),(g,i),(b,c),(d,e),(a,f),(h,j),(a,e),(f,i),(g,j),(c,h),(b,g),(d,i).五、證明題（每小題10分，共20分） 1. 證： 設ab的階等于n，即。 (2分)于是，。 (5分)故，得ba的階小于等于n。 (7分)即ba的階小于等于ab的階。類似可得ab的階小于等于ba的階。 (9分)于