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

2009-2010学年第二学期　 考试科目：　 离散数学 　　 考试类型：（闭卷）考试　　　 考试时间：　120 分钟 学号 姓名 年级专业 得分 一、判断题（本大题共10小题，每小题1分，共10分） 1、“如果天气好，那么我去散步既是合取范式也是析取范式。 4、是前束范式。 5、A，B，C都是集合，如果A∪B=A∪C，则B=C。 6、和是集合A上的具有自反性的关系，则也一定具有自反性。 7、顶点数目相同，边数也相同的两个无向图一定同构。 8、每个顶点的度数都是偶数的无向图一定是欧拉图。 9、奇数阶完全图一定是欧拉图。 10、二阶以上连通没有回路的无向图是二部图。 得分 二、选择题（本大题共15小题，每小题2分，共30分） 1、下面语句是简单命题的为_____。 A、3不是偶数。 B、李平既聪明又用功。 C、李平学过英语或日语。 D、李平和张三是同学。 2、下列命题公式中是矛盾式的有_____。 A、 B、 C、 D、 3、下列集合不是连接词极小全功能集的为_____。 A、{?,∧,∨} B、{?,→} C、{↓} D、{↑} 4、下列谓词公式不是命题公式P→Q的代换实例的是______ A、 B、 C、 D、 5、设个体域为整数集，下列公式中其值为1的是_____。 A、 B、 C、 D、 6、下列哪个表达式错误_____。 A、 B、 C、 D、 7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是____。 A、1(A B、{{4,5}}(A C、{1,2,3}(A D、((A 8、设集合，集合，则 ____。 A、 B、 C、 D、 9、设集合上的两个关系，则R具有____。 A、对称性 B、传递性 C、自反性 D、反自反性 10、下述结论错误的是____。 A、存在这样的关系，它可以既满足对称性，又满足反对称性。 B、存在这样的关系，它可以既不满足对称性，又不满足反对称性。 C、存在这样的关系，它可以既满足自反性，又满足反自反性。 D、存在这样的关系，它可以既不满足自反性，又不满足反自反性。 11、集合A上的关系R为一个等价关系，当且仅当R具有_____。 A、自反性、对称性和传递性 B、自反性、反对称性和传递性 C、反自反性、对称性和传递性 D、反自反性、反对称性和传递性 12、以下整数序列，能成为一个简单图的顶点度数序列的是_____。 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 13、设无向图G的关联矩阵为，则G的顶点数与边数分别为_____。 (A)4, 5 (B)4, 10 (C)5, 4 (D)5, 10 14、以下无向图中，不是二部图的是_____。 A、 B、 C、 D、 15、以下无向图中，不是欧拉图的是_____。 A、 B、 C、 D、 得分 三、填空题（本大题共10小题，每小题2分，共20分） 1、设 p:天冷，q:小王穿羽绒服，将命题“除非天冷，小王才穿羽绒服”符号化 (1)___。 2、命题公式的对偶式是 (2)___。 3、p→q 的主合取范式是 (3)___。 4、设G(x)：x爱美，F(x)：x为人，在全总个体域中将命题“人都爱美”符号化 (4)___。 5、设F(x)：x是兔子， G(y)：y是乌龟，H(x,y)：x比y跑得快，在全总个体域中将命题“有的兔子比所有的乌龟跑得快”符号化 (5)___。 6、设集合，集合，则 (6)___。 7、设集合，则 (7)___。 8、设集合A={1, 2, 3, 4}，R=={1,1, 1,3, 2,3, 3,2, 3,3}和S={1,2, 1,4, 2,2, 2,3}是集合A上关系，则R○S= (8)___。 9、设无向图G有12条边，2，3，4，5，6度顶点各1个，其余顶点均为悬挂顶点(即1度顶点)，则G中有 (9)___个悬挂顶点。 10、完全二部图的匹配数是 (10)___。 得分 四、计算题（本大题共2小题，每小题