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

200920010学年第一学期计算机学院08级离散数学期末考试试卷（A卷）年级专业 班级 学号 姓名 注：考试时间共120分钟，试卷总分100分 题号一二三四五六总分签名得分一得 分一、 选择题（每小题2分，共20分）1. X=1,2,3,4,5, R=,Ix ,则X/R=_。A. B. C. D. 2. 设表示“是学生。”，表示“考试及格。”， 则对命题“有的学生考试不及格.”可符号化为_ _。A. B. C. D. 3下列无向图中不是欧拉图的是 。 A. B. C. D. 4. A= a,b,c, f=， 则f是A上的 。A. 单射但不是满射 B. 是满射但不是单射 C. 双射 D. 非单射也非满射5. 设，则关于如下_定义的*运算不能构成半群。A. B. C. D. 6. 一个5阶简单平面图G最多有_ _条边。 A. 7 B. 8 C. 9 D. 107. 公式中, 约束出现和自由出现的次数分别为 。 A. 1和2 B. 2和1 C. 3和1 D. 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的主合取范式为，则A的成真赋值为 ，公式类型为 。2.是含幺环,则是 ， 是 。3.设 集合, B=a,b,则_ _ _,=_。4. 设E=1,2，3,4,5,6,A=x|x4, B=x|1x5,则 ,_。5. 有n个顶点、k棵树的森林共有 条边，n个点的有向完全图共有 条边。6. A=1,2,3,4, R=,S=,则 _ ， _ _ _。7. 的前束范式是 。8. S=1,2,3,4, S上的置换，则 。 。9Q为有理数集，运算+是普通加法，则群Q，+上 ， 。10一棵无向树T有2个2度结点，3个3度结点，1个4度结点，其余为叶。则T共有 个结点， 片叶。离散数学期末考试试卷（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分) 已知偏序集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的邻接矩阵；(4).求出图中所有长度小于等于2的回路的条数。六得 分六、证明题（每小题10分，共20分）1给出下列推理证明的规则前提：，结论：证明:(1) _;(2) _;(3) _;(4) _;(5) _; (6) _;(7) _; (8) _;(9) _。2