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

《离散数学（下）》试卷第1页共6页安徽大学2009—2010学年第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.M2(R)=为实数域R,Rb,a0b0a按矩阵的加法和乘法构成R上的二阶方阵环,这个方阵环是()A.有幺元的交换环B.无幺元的非交换环C.无幺元的交换环D.有幺元的非交换环4.下列说法不正确的是（）A．两个域的直接乘积是域B.有限整环是域C．n次对称群nS的阶是!nD.域只有平凡理想5.下列整数集对于整除关系都构成偏序集，而能构成格的是（）A．{l，2，3，4，6}B．{1，2，3，6，12}C．{2，3，6}D．{l，2，3}6．记N是自然数集，≤是小于等于关系，则N,≤是().A.有界格B.有补格C.分配格D.有补分配格7.在布尔代数1,0,,,,B上定义的n元布尔表达式所对应的不同主析取范式总个数为（）A．n2B.nBBC.nB2D.nB题号一二三四五总分得分阅卷人院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------得分《离散数学（下）》试卷第2页共6页8.无向图的关联矩阵中“关联”指的是()。A.结点与结点的关联B.边与边的关联C.边与结点的关联D.都不是9.设G是具有n个结点m条边，k个面的连通平面图，其中2m，则有（）成立。A．2kmnB．63nmC．1nmD．42nm10.设G是由5个结点组成的无向完全图，则从G中删去（）条边可以得到树。A．4B．5C．6D．10二、判断题（对的打√，错的打×，每小题2分，共10分）1.若群G的每个元素都满足方程x2=e，其中e为幺元，则G为交换群。（）2.若群G的阶为n，d为n的一个因子，则G一定有阶为d的子群。（）3.如果环R满足左消去律，则R必定没有右零因子。（）4.设G=V,E是无向简单图,G的极小支配集都是G的极大独立集。（）5.设G是有10个结点的无向图，对于G中任意两个不邻接的结点u和v,均有9degdegvu，则G是哈密尔顿图。（）三、填空题（每小空2分，共20分）1.设G是由12个元素构成的循环群，a是G的一个生成元素，则G有_______个非平凡子群。G的生成元素集合是_________。2.设H是群G的子群，Gba,，则HbHa的充要条件是___________________。3.设a,b分别是群G的3阶和5阶元，且ab=ba，则ab的阶为__________。4.整数环有__________个可逆元。5.如果一个格中存在全上界和全下界，则这个格是________________。6．所有模格组成的集合_________（填,或）所有分配格组成的集合。得分得分《离散数学（下）》试卷第3页共6页7．设G是),(pp连通图，则G的生成树的个数至多为____________。8．含5个结点、3条边的不同构的无向简单图个数为________。9．设无向图G有12条边，有6个3度结点，其余结点度数均小于3，则G中结点数至少为______。四、解答题（每小题10分，共30分）1.给出一个含有四个四元置换的集合4321,,,G,其中,34124321,43124321,34214321,432143214321,G在合成运算下组成的群,G，试求,G的所有正规子群，并且求,G关于每个正规子群的商群及各商群中的运算表。得分答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------《离散数学（下）》试卷第4页共6页2.设1,0,,,,B为一布尔代数，Bcba,,，试化简布尔表达式)(bacbaa。3.给定彼得森(Petersen)图G如右图所示。试求图G的支配数)(0G、点覆盖数)(0G、边覆盖数)(1G、独立数)(0G、匹配数)(1G、点连通度)(0G、边连通度)(1G、点色数)(0G、边色数)(1G，以及邻接矩阵A（结点与自身邻接，结点次序按字母顺序）。)(0G)(0G)(1G)(0G)(1G)(0G)(1G)(0G)(1G《离散数学（下）》试卷第5页共6页五、证明题（每小题10分，共20分）1.设G是群，a,b是G中任意两个元素，则ab的阶与ba的阶相同。2.设T是一棵树且kT)(，证明：T中至少有k个结点的度为1。得分答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------《离散数学（下）》试卷第6页共6页安徽大学2009—2010学年第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.×；5.×。三、填空题（每小空2分，共20分）1.4;{a,a3,a5,a7,a11};2.Hab1（或Hba1）;3.15;4.2;5.有界格;6.;7.p;8.4;9.9.四、计算题（每小题10分，共30分）1.解：,G的正规子群有,1、,G、,,21、,,31、,,41。（5分）,1的商群为*,,,,4321，其中*运算表为：（6分）*123411234221433341244321,G的商群为*,G，其中*运算表为：（7分）*GGG,,21的商群为*,,,,4321，其中*运算表为：（8分）*21,43,21,21,43,43,43,21,,,31的商群为*,,,,4231，其中*运算表为：（9分）*31,42,31,31,42,42,42,31,,,41的商群为*,,,,3241，其中*运算表为：（10分）*41,32,41,41,32,32,32,41,《离散数学（下）》试卷第7页共6页2.解：（共10分）)(bacbaa＝baacbaa(2分)＝baa(6分)＝babaaa)()((10分)3.解:（每空1分，共10分）)(0G)(0G)(1G)(0G)(1G)(0G)(1G)(0G)(1G365453334邻接矩阵:最小支配集：{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，即eabn。(2分)于是babbn，bbban。(5分)故eban，得ba的阶小于等于n。(7分)即ba的阶小于等于ab的阶。类似可得ab的阶小于等于ba的阶。(9分)于是ab的阶等于ba的阶。(10分)2.证：设T中有p个结点，s个树叶，(2分)则T中其余ps个结点的度数均大于等于2，(4分)且至少有一个结点的度大于等于k。可得：(6分)1222()2(1)piiqpdegvpsks，有sk。(8分)所以T中至少有k个树叶。(10分)1011010000010110100010101001001101000010011010000110000110010100011100001000111000010001110000110011A