10信管离散数学考试卷(A)

2010－2011学年第二学期计算机学院10信管《离散数学》期末试卷（A卷）年级＿＿＿专业＿＿＿＿＿＿班级学号＿＿＿＿姓名＿＿＿注：考试时间共120分钟，试卷总分100分题号一二三四五六总分签名得分一得分一、选择题（每小题2分，共20分），请将所选答案填入下表中。题号12345678910答案1.以下语句中_____是命题.A.这次考试太难了!B.0yx.C.不经历风雨就不能见彩虹.D.1+1什么时候等于3?2.命题公式qqp)(是______.A.重言式B.矛盾式C.非重言式的可满足式D.析取范式3．A={a,b,c},},,,{bccaR，则R是A上的。A.传递关系B.对称关系C.自反关系D.反对称关系4.设)(xS表示“x是学生。”，)(xP表示“x考试及格。”，则对命题“不是所有的学生考试都及格了.”可符号化为______。A.))()((xPxSxB.))()((xPxSxC.))()((xPxSxD.))()((xPxSx5.设)|{ZxxA，则A关于如下_____定义的*运算不能构成半群。A.xyxB.yxyxC.),min(yxyxD.),max(yxyx6.一个6阶简单平面图，最多有____边数。A.10B.11C.12D.137.有11个顶点、3棵树的森林共有条边。A.6B.7C.8D.98.以下图中不是哈密顿图的是。A．4KB.5KC.3,3KD.2K9.设F={-1，1}，运算是普通乘法，则(F,)。A.是独异点但不是群B.是群但不是阿贝尔群C.是阿贝尔群但不是循环群D.是阿贝尔群并且是循环群10.设E={1,3,4,5,6，7},A={x|x4},B={x|3x6},则BA____。A.{1，4}B.{1，2，4}C.{1，3，4,5}D.{1，2，3，4,5}二得分二、填空题（本大题共10小题，每小题3分，共30分）1.含两个变元p,q的命题公式A的成真赋值为00，11，则A的主合取范式为。A的类型为。2．公式)),(),((),(yxHyxGyyxF中,y的辖域是，y自由出现次。3.设集合},{baA,}2,1{B,则BA=__________________。)(A。4.Q为有理数集，运算+是普通加法，则群〈Q，+〉上，12=，31。5.6个点4条边3个面的平面图共有个连通分支。n个点m条边k个面的连通平面图的欧拉公式为。6.A={1,2,3,4},R={3,3,1,2},)(Rr___，)(Rt。7．欧拉图共有个奇点，无向完全图6K共有条边。8.X={1,2,3,4,5},X上的等价关系R={4,5,5,4}∪Ix,则[4]R=___________,X/R=__________________________.9．G是交换群，则其运算满足、、消去律。10．S={1,2,3,4},S上的置换)132(，)24)(13(，则。1。《离散数学》期末考试试卷（A卷）第1页共3页三得分三、判断题（错的打“×”，对的打“√”；每小题1分，共10分。）1.无向图G是哈密顿图，则G一定是连通图。（）2.命题公式)qq是重言式。（）3.循环群一定是交换群。（）4.零元一定没有逆元。（）5.一个关系是自反的就一定不是反自反的。（）6．f，g是A上的函数，若gf是双射，则g一定是满射。（）7．一个有5个结点，4条边的无向图是树。（）8．关系的复合满足结合律。（）9．A的等价关系与A的划分一一对应。（）10．一个公式的主析取范式与主合取范式是等值的。（）四得分四.(每小题6分,共12分)1．一棵无向树T有5个2度结点，2个3度结点，3个4度结点，其余为叶。则T共有多少个结点，多少片叶？2．求公式rqp)(的主析取范式和主合取范式五得分五（每小题8分，共16分）1、(10分)已知偏序集〈X,R〉,其中X={2,3，4,6,12，24},R为X上的的整除关系，Y={4，6}①画出R的哈斯图；②.找出X的极大元、极小元、最大元、最小元；③.找出Y的上界、下界、最小上界、最大下界。《离散数学》期末考试试卷（A卷）第2页共3页2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,a,a,b,a,ca,d,b,a,b,d,c,a,c,b，c,c，c,d,d,c,d,d}(1).求出G中顶点的入度序列。(2).写出G的邻接矩阵；(3).求出图中所有长度等于2的路的条数。六得分六、证明题（每小题6分，共12分）1．构造下面推理的证明：rsqprp,,.qs2．S={0,1,2,…,n-1},在S上定义二元运算:xy=(x+y)modn,其中+、-是普通加法、减法，证明S，是循环群。《离散数学》期末考试试卷（A卷）第3页共3页