离散数学考试卷(A10)

《离散数学》期末考试试卷（A卷）第1页共5页2010－2011学年第二学期计算机学院《离散数学》期末试卷（A卷）年级专业班级学号姓名注：考试时间共100分钟，试卷总分100分题号一二三四五六总分签名得分一得分一、填空题（本大题共10小题，每小题3分，共30分）1.设命题公式)(RQPG，则使G成真指派分别是。2．公式),()),(),((yxHyxyGyxFx中,y的辖域是，x自由出现次。3.设集合},{baA,}2,1{B,则BA=__________________。)(A。4.Q为有理数集，运算+是普通加法，则群〈Q，+〉上，23，32。5.把置换561342654321表成轮换的乘积是，表成对换的乘积是。6.A={1,2,3,4},R={3,3,1,2,2,4},)(Rs___，)(Rt。7．欧拉图共有个奇点，无向完全图6K共有条边。8.X={a,b,c,d,e},X上的等价关系R={a,b,b,a,d,e,e,d}∪Ix,则[b]R=___________,X/R=__________________________.9．偏序关系具有的性质是、、。10．有甲乙丙三个人猜测ABC三个球队中的冠军.各人的猜测如下:《离散数学》期末考试试卷（A卷）第2页共5页甲:冠军不是A,也不是B；乙:冠军不是A,而是C；丙:冠军不是C,而是A。已知其中有一个人说的完全正确.一个人说的都不对,而另外一人恰有一半说对了.据此推算,冠军应该是。二得分二、选择题（每小题2分，共20分，请将所选答案填入下表中。）题号12345678910答案1.以下语句中_____是命题.A.禁止酒后驾车!B.06x.C.三亚是海南的省会.D.0是偶数吗?2.命题公式qqpp))((是______.A.重言式B.矛盾式C.非重言式的可满足式D.析取范式3．A={1,2,3},AIR}1,3,3,1{，则R是A上的.A.等价关系B.偏序关系C.反自反关系D.对称关系4.设)(xP表示“x是运动员”，)(xQ表示“x会跳水”则“并非所有的运动员都会跳水。”可翻译成______.A.))()((xQxPxB.)()(xQxxPC.))()((xQxPxD.))()((xQxPx5.设)|{ZxxA，则A关于如下_____定义的*运算不能构成半群。A.xyxB.yxyxC.),min(yxyxD.),max(yxyx6.一个5阶简单平面图，最多有____边数。A.6B.7C.8D.97.有12个顶点、3棵树的森林共有条边。A.6B.7C.8D.98.设集合cbaA,,，A上的二元关系bbaaR,,,不具备性质。A.传递性B.反对称性C.对称性D.自反性9.设F={-1，0，1}，运算是普通乘法，则F,。A.是独异点但不是群B.是群但不是阿贝尔群《离散数学》期末考试试卷（A卷）第3页共5页C.是阿贝尔群并且是循环群D.是阿贝尔群但不是循环群10.设集合dcCcbaBA,,,,,2,1，则)(CBA。A.cc,2,1,B.cc,2,,1C.2,,1,ccD.2,,,1cc三得分三、判断题（错的打“×”，对的打“√”；每小题1分，共10分）1.若有向图G是单向连通的，则必是强连通的。（）2.命题公式qq不是重言式。（）3.循环群一定是交换群。（）4.群中一定没有零元。（）5.一个关系是对称的就一定不是反对称的。（）6．f，g是A上的函数，若gf是双射，则g一定是双射。（）7．无向图G是哈密顿图，则G一定是欧拉图。（）8．关系的复合满足结合律。（）9．A的等价关系与A的划分一一对应。（）10．一个有5个结点，4条边的无向连通图是树。（）四得分四、(每小题6分,共12分)1．求公式rqp)(的主析取范式和主合取范式。《离散数学》期末考试试卷（A卷）第4页共5页2．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。试求其共有多少个结点？多少片叶？五得分五（每小题10分，共20分）1、(10分)已知偏序集〈X,R〉,其中X={a,b,c,d,e},Y={d,e},R的关系矩阵为求：(1).用集合的列举法写出R；(2).画出R的哈斯图；(3).找出X的极大元、极小元、最大元、最小元；(4).找出Y的上界、下界、最小上界、最大下界。1011111111001000011000101RM《离散数学》期末考试试卷（A卷）第5页共5页2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,a,a,ba,d,b,a,b,b,c,a,c,b，c,c，c,d,d,c,d,d}(1).求出G中顶点的入度序列；(2).写出G的邻接矩阵；(3).求出图中所有长度等于2的路的条数。六得分六、证明题（8分，）构造下面推理的证明：前提：sqrpqp,,结论：rs