安徽大学计算机学院2009—2010年离散数学(下)A卷试卷

《离散数学（下）》第1页共4页安徽大学2009—2010学年第2学期《离散数学（下）》考试试卷（A卷）（闭卷时间120分钟）一、单项选择题（每小题2分，共20分）1．设R为实数集合，则下列集合关于加法运算不是,R的子代数的是（）A.偶数集合；B.奇数集合；C.自然数集合；D.整数集合。2．下列关于群的说法正确的是（）A.质数阶的群必为循环群；B.有限群必为循环群；C.循环群必为质数阶群；D.循环群必为有限群。3．设R为实数集合，则20(),0aMRabRb关于矩阵的乘法运算（）A.可交换且有么元；B.可交换且无么元；C.不可交换且有么元；D.不可交换且无么元。4．设I为整数集合，则下列关系是代数,I上的同余关系的是（）A.||0xyxy；B.(00)(00)xyxyxy；C.xyxy；D.(0)(00)xyxyxy。5．下列集合关于整除关系构成格的是（）A.{1,2,3,4,6}；B.{1,2,3,6}；C.{2,3,6}；D.{1,2,3}。6．在布尔代数,,,,0,1B中任取两元素,ab，下列命题与ab不一定等价的是（）A.aba；B.abb；C.0ab；D.1ab。7．布尔代数1,0,,,,B上定义的n元布尔表达式所对应的不同主析取范式总个数为（）A.n2；B.nBB；C.nB2；D.nB。8．设无向图,GVE中{1,2,3,4,5}V，{(1,2),(2,3),(3,4),(4,5),(5,1),(2,5)}E，则{2,4}V不是图G的（）A.点割；B.支配集；C.点覆盖；D.独立集。9．设G是具有n个结点、m条边和k个面的连通平面图，则下列公式一定成立的是（）A.2nkm；B.36mn；C.1mn；D.24mn。10．设G是由5个结点组成的无向完全图，则G的生成树比G的边数少（）A.4条；B.5条；C.6条；D.10条。题号一二三四五总分得分阅卷人院/系年级专业姓名学号答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------得分《离散数学（下）》第2页共4页二、判断题（对的打√，错的打×，每小题2分，共10分）1．代数中的可逆元一定是可约元。（）2．有补格中任何元素的补元必唯一。（）3．有限群中任何元素的阶必整除群的阶。（）4．无向简单图的极小支配集一定是极大独立集。（）5．无向简单连通图的连通度一定不小于其点连通度。（）三、填空题（每小空2分，共20分）1．设Ga为12阶循环群，则G有个子群，个生成元；G中元素8a的阶为，G中元素4a的逆元为。2．有全上界和全下界的格称为；布尔代数中覆盖全下界的元素称为。3．无向完全图5K欧拉图，二部图。（填“是”或“不是”）4．n个结点的无向树中至少有片树叶，至多有片树叶。四、解答题（每小题10分，共30分）1．设1,0,,,,B为布尔代数，Bcba,,，化简布尔表达式)(bacbaa。2.求彼得森(Petersen)图G（如下图所示）的支配数)(0G、点覆盖数)(0G、边覆盖数)(1G、独立数)(0G、匹配数)(1G、点连通度)(0G、边连通度)(1G、点色数)(0G、边色数)(1G，结果填入下表；并给出图G的邻接矩阵A（结点与自身邻接，结点次序按字母顺序）。)(0G)(0G)(1G)(0G)(1G)(0G)(1G)(0G)(1G得分得分得分《离散数学（下）》第3页共4页3．设4321,,,G为含有4个四元置换的集合，其中34124321,43124321,34214321,432143214321，则G在合成运算下构成群,G。求群,G的所有正规子群及对应的商群，给出各商群的运算表。答题勿超装订线------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------《离散数学（下）》第4页共4页五、证明题（每小题10分，共20分）1.证明：对于群,G中的任意两个元素,ab，ab的阶与ba的阶相同。2.设T是一棵树且kT)(，证明：T中至少有k个结点的度为1。得分