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

《08本离散数学考试卷(A)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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.B.C.D.2.设表示“是学生。”，表示“考试及格。”，则对命题“有的学生考试不及格.”可符号化为______。A.B.C.D.3．下列无向图中不是欧拉图的是。A.B.C.D.4.A={a

2、,b,c},f={，，}，则f是A上的。A.单射但不是满射B.是满射但不是单射C.双射D.非单射也非满射5.设，则关于如下_____定义的*运算不能构成半群。A.B.C.D.6.一个5阶简单平面图G最多有____条边。A.7B.8C.9D.107.公式中,约束出现和自由出现的次数分别为。A.1和2B.2和1C.3和1D.1和38.R是A上的偏序关系,则R有的性质是.A.自反性、对称性、传递性B.自反性、反对称性、传递性C.反自反性、对称性、传递性D.反自反性、反对称性、传递性9.设F={-1，0,1}，运算·是普

3、通乘法，则(F,·)。A.是独异点但不是群B.是群但不是阿贝尔群C.是阿贝尔群但不是循环群D.是阿贝尔群并且是循环群10.在根树中，若结点a到结点b有边，b到c也有边，则a是c的____。A.双亲B.兄弟C.子孙D.祖先二得分二、填空题（本大题共10小题，每小题2分，共20分）1.有两个变元的命题公式A的主合取范式为，则A的成真赋值为，公式类型为。2.是含幺环,则是，是。3.设集合,B={a,b},则_______________,=_____________________。4.设E={1,2，3,4,5,

4、6},A={x

5、x<4},B={x

6、1,<1,2>,<2,4>},S={<1,3>,<2,4>,<4,2>}则{______________}，___________。7.的前束范式是。8.S={1,2,3,4},S上的置换，，则。。9．Q为有理数集，运算+是普通加法，则群〈Q，+〉上，。10．一棵无向树T有2个2度结点，3个3度结点，1个4度结点，其余为叶。则T共有个结点，片

7、叶。《离散数学》期末考试试卷（A卷）第3页共1页三得分三、判断题（错的打“×”，对的打“√”；每小题1分，共5分。）1.一个有向哈密顿图一定是连通图。（　）2.　A上的函数f如果是单射，则一定是满射。（）3.命题公式是重言式。（）4.　零元一定没有逆元（）　　　　　　　　　　　5.　一个对称关系一定不是反对称的。（）四得分四.(每小题5分,共15分)1．已知X={1，2，3},写出X上的所有双射。2．画出一棵叶权为2，2，2，3，3，4的最优二叉树并计算出树权。3．求公式的主析取范式和主合取范式五得分五（每小题10分，共20分）1、(10分)

8、已知偏序集〈X,R〉,其中X={a,b,c,d,},Y={a,b},R的关系矩阵为1.用集合的列举法写出R;2.画出R的哈斯图；3.找出X的极大元、极小元、最大元、最小元；4.找出Y的上界、下界、最小上界、最大下界。《离散数学》期末考试试卷（A卷）第2页共3页2．已知有向图G=,其中v={a,b,c,d}，E={,,,,,,,,}(1).求出图的顶点的入度序列、出度序列；(2).判定图G是否为欧拉图？，是否哈密顿图？并说明理由；(3).写出G的

9、邻接矩阵；(4).求出图中所有长度小于等于2的回路的条数。六得分六、证明题（每小题10分，共20分）1．给出下列推理证明的规则前提：，结论：证明:(1)_________________;(2)_________________;(3)_________________;(4)__________________;(5)_________________;(6)________________;(7)________________;(8)__________________;(9)___________________。2．Zn={0,1,

10、2,…,n-1},在Zn上定义二元运算·:x·y=(x+y)modn,其中+、-是普通加法、减法，证明是循环群。《离散数学》期末考试试卷（A卷）第3页共