离散数学期末考试试卷2.doc

2009-2010学年第二学期　 考试科目：　 离散数学 　　 考试类型：（闭卷）考试　　　 考试时间：　120 分钟 学号 姓名 年级专业 得分 一、判断题（本大题共10小题，每小题1分，共10分） 1、五阶完全图既是欧拉图，也是哈密顿图。 2、设无向图T是树，则T中一定没有简单回路。 3、“如果天气好，那么我去散步既是合取范式也是析取范式。 6、是前束范式。 7、A，B，C都是集合，如果A∪B=A∪C，则B=C。 8、和是集合A上的具有自反性的关系，则也一定具有自反性。 9、顶点数目相同，边数也相同的两个无向图一定同构。 10、每个顶点的度数都是偶数的无向图一定是欧拉图。 得分 二、选择题（本大题共15小题，每小题2分，共30分） 1、下面语句是真命题的为_____。 A、我正在说谎。 B、如果1＋1＝2，则太阳从西边升起来。 C、如果1＋1＝3，则太阳从西边升起来。 D、吃饭了吗？ 2、命题公式P→(Q→P)为_____。 A、重言式 B、可满足式 C、矛盾式 D、等值式 3、下面联结词不具有交换律的是_____。 A、∧ B、∨ C、→ D、( 4、设I是如下一个解释，，其中，为真，，为假，则在解释I下取真值的公式是______ A、 B、 C、 D、 5、下列哪个表达式错误_____。。 A、 B、 C、 D、 6、设集合上的两个关系，则R具有____。 A、自反性 B、传递性 C、对称性 D、反自反性 7、下述结论错误的是____。 A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。 8、设偏序集（）关系R的哈斯图如右所示，若A的子集，则元素6为B的_____。 A、下界 B、上界 C、最小上界 D、以上都不对 9、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 A、1，2，2，3，4，5 B、2，3，3，4，4，5 C、2，2，3，4，5，6 D、1，2，2，3，3，5 10、设图G是有6个顶点的连通图，总度数为16，则从G中删去_____条边后可以使之成为树。 A、10 B、5 C、3 D、2 11、在下列关于图论的命题中，正确的是_____。 A、哈密顿图一定是欧拉图 B、无向完全图都是欧拉图 C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出 D、哈密顿图是平面图 12、下面编码_____不是前缀码。 A、11，00，10，01 B、01，11，011，1001 C、101，11，001，011，010 D、010，11，011，1011，1001，10101 13、6阶非同构的无向树有_____棵。 A、5 B、6 C、7 D、8 14、实数集关于下列二元运算结合律交换律。 B、 C、 D、 15、在下列选项中，不是群的是_____。 A、，为有理数，+为加法运算 B、，为非零实数集，为乘法运算 C、，为实数集，+为加法运算 D、，为有理数，*为乘法运算 得分 三、填空题（本大题共10小题，每小题2分，共20分） 1、设P：1+1=2，Q：2是偶数，将命题“1+1=2，仅当2是偶数”符号化 (1)___。 2、在公式中，约束出现的变元为 (2)___。 3、给定集合上的3个关系如下： ，， ， 则其中满足对称性的关系是 (3)___； 4、非空集合A上的自反、 (4)___和传递的关系称为A上的偏序关系。 5、后缀表达式 3 5 2 － * 7 + 4 / 的值是 (5)___。 6、设无向图G有11条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (6)___个悬挂顶点。 7、设G为连通的平面图，有5个面，总度数为14，则G有 (7)___个顶点。 8、已知一棵无向树T中有4度、3度和2度分支点各1个，其余顶点