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页

1 / 6
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功