离散数学(下)A卷和参考答案及评分标准

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分)于