08本离散数学考试卷(A)

2009－20010学年第一学期计算机学院08级《离散数学》期末考试试卷（A卷）年级＿＿＿专业＿＿＿＿＿＿班级学号＿＿＿＿姓名＿＿＿注：考试时间共120分钟，试卷总分100分题号一二三四五六总分签名得分一得分一、选择题（每小题2分，共20分）1.X={1,2,3,4,5},R={1,2,2,1,3,5,5,3}∪Ix,则X/R=____。A.}5,4,3{},2,1{B.}5,4{},3,2,1{C.}4{},5,3{},2,1{D.}5{},4,3{},2,1{2.设)(xS表示“x是学生。”，)(xP表示“x考试及格。”，则对命题“有的学生考试不及格.”可符号化为______。A.))()((xPxSxB.))()((xPxSxC.))()((xPxSxD.))()((xPxSx3．下列无向图中不是欧拉图的是。A.3,3KB.3KC.4,2KD.5K4.A={a,b,c},f={a，a，b，c，c，b}，则f是A上的。A.单射但不是满射B.是满射但不是单射C.双射D.非单射也非满射5.设)|{ZxxA，则A关于如下_____定义的*运算不能构成半群。A.xyxB.yxyxC.),min(yxyxD.),max(yxyx6.一个5阶简单平面图G最多有____条边。A.7B.8C.9D.107.公式),()),(),((yxHyxyGyxFx中,y约束出现和自由出现的次数分别为。A.1和2B.2和1C.3和1D.1和38.R是A上的偏序关系,则R有的性质是.A.自反性、对称性、传递性B.自反性、反对称性、传递性C.反自反性、对称性、传递性D.反自反性、反对称性、传递性9.设F={-1，0,1}，运算是普通乘法，则(F,)。A.是独异点但不是群B.是群但不是阿贝尔群C.是阿贝尔群但不是循环群D.是阿贝尔群并且是循环群10.在根树中，若结点a到结点b有边，b到c也有边，则a是c的____。A.双亲B.兄弟C.子孙D.祖先二得分二、填空题（本大题共10小题，每小题2分，共20分）1.有两个变元的命题公式A的主合取范式为20MM，则A的成真赋值为，公式类型为。2.R,+,*是含幺环,则R,+是，R,+是。3.设集合},{dcA,B={a,b},则)(A_______________,BA=_____________________。4.设E={1,2，3,4,5,6},A={x|x4},B={x|1x5},则BA,BA____________________。5.有n个顶点、k棵树的森林共有条边，n个点的有向完全图共有条边。6.A={1,2,3,4},R={3,3,1,2,2,4},S={1,3,2,4,4,2}则)(1RtR{______________}，SR___________。7.)()(xxGxxF的前束范式是。8.S={1,2,3,4},S上的置换)124(，)24)(13(，则。1。9．Q为有理数集，运算+是普通加法，则群〈Q，+〉上32，14。10．一棵无向树T有2个2度结点，3个3度结点，1个4度结点，其余为叶。则T共有个结点，片叶。《离散数学》期末考试试卷（A卷）第3页共1页三、判断题（错的打“×”，对的打“√”；每小题1分，共5分。）1.一个有向哈密顿图一定是连通图。（）2.A上的函数f如果是单射，则一定是满射。（）3.命题公式qq是重言式。（）4.零元一定没有逆元（）5.一个对称关系一定不是反对称的。（）四.(每小题5分,共15分)1．已知X={1，2，3},写出X上的所有双射。2．画出一棵叶权为2，2，2，3，3，4的最优二叉树并计算出树权。三得分四得分3．求公式qpr)(的主析取范式和主合取范式五得分五（每小题10分，共20分）1、(10分)已知偏序集〈X,R〉,其中X={a,b,c,d,},Y={a,b},R的关系矩阵为1.用集合的列举法写出R;2.画出R的哈斯图；3.找出X的极大元、极小元、最大元、最小元；4.找出Y的上界、下界、最小上界、最大下界。《离散数学》期末考试试卷（A卷）第2页共3页1000010011111101RM2．已知有向图G=V,E,其中v={a,b,c,d}，E={a,b,b,a,b,c,b,b,b,d,c,a,c,d,d,c,d,d}(1).求出图的顶点的入度序列、出度序列；(2).判定图G是否为欧拉图？，是否哈密顿图？并说明理由；(3).写出G的邻接矩阵；(4).求出图中所有长度小于等于2的回路的条数。六得分六、证明题（每小题10分，共20分）1．给出下列推理证明的规则前提：))()((,)))()(()((xPxRxxRxQxPx，结论：)(xxQ证明:(1)))()((xPxRx_________________;(2))()(cPcR_________________;(3))))()(()((xRxQxPx_________________;(4)))()(()(cRcQcP__________________;(5))(cP_________________;(6))()(cRcQ________________;(7))(cR________________;(8))(cQ__________________;(9))(xxQ___________________。2．Zn={0,1,2,…,n-1},在Zn上定义二元运算·:x·y=(x+y)modn,其中+、-是普通加法、减法，证明Zn，·是循环群。《离散数学》期末考试试卷（A卷）第3页共3页