浙江工业大学2007/2008学年
第二学期 试卷
课程 《离散数学II》 姓名__________________________ 班级___________________________ 学号__________________________
题序 计分 一 二 三 四 五 总评 第1页，共5页 一、选择题（每题2分，共20分） 1．S={0,1}；*是普通乘法，代数系统不能构成 ( )。 A．群 B．独异点 C．半群 D．代数系统 2．已知 Z6={0，1，2，3，4，5}，代数系统是 ( )。 A．无零因子环 B．域 C．含幺环 D．整环 3．设既是一个有界格，也是有补格，则只要满足 ( )。 A．每个元素都有一个补元 B．每个元素都至少有一个补元 C．每个元素都无补元 D．每个元素都有多个补元 4．设G是由5个顶点组成的完全图，则从图G中删去几条边可以得到树。( ) A．6 B．5 C．8 D．4 5．下述偏序集能构成格的是( )。 (1) (2) (3) A．(1)(2) B．(1)(3) C．(2)(3) D．(1)(2)(3) 6．7个顶点的非同构的无向树有几棵。( ) A．8 B．6 C．11 D．5 7．连通图G是一棵树当且仅当G中。 ( ) A．有些边不是割边 B．每条边都是割边 C．无割边集 D．每条边都不是割边 浙 江 工 业 大 学 考 试 命 题 纸
第2页，共5页 8．﹡运算如下表所示，哪个能使<{a,b}，﹡>成为独异点 ( )。?A.a bB.?a bC.?a b?a ba a bb a ba a ab b ba a ab a aD.a a bb b a 9．设Z是整数集合，+是一般加法，则下述函数中哪个不是群的自同态。( ) A．f?x??2x B． f?x??1000x C． f?x??x D． f?x??0 10．n（n≥3）阶无向树既是简单图又是二部图。 ( ) 二、判断题（每题1分，共10分） 1．在整数环中定义*和◇两个运算，a,b∈Z 有 a*b = a+b-1, a◇b = a+b-ab。则构成环。 ( ) 2．设无向图G中只有两个奇度顶点u与v，则u与v不一定连通。( ) 3．设G是循环群，G同构于H，则H不一定是循环群。 ( ) 4．A关于*有幺元，当且仅当该元素所对应的行和列依次与运算表的行列相一致。( ) 5．下图为哈密尔顿图。( ) 6．对于给定的集合和二元运算来说，如果单位元或零元存在，则是惟一的。( ) 7．哈密尔图一定不是平面图。 ( ) 8．简单图没有平行边，没有环。 ( ) 9．偏序集10．设Z为整数集， 是布尔格。 ( ) x,y∈Z,x·y=x+y-2，则Z关于·运算构成群。( ) 浙 江 工 业 大 学 考 试 命 题 纸
第3页，共5页
三、填空题（每空2分，共18分） 1．设Z18为模18整数加群, 求元素5的阶 。 2．设 是格，其中A={1,2,3,4,6,12}，?为整除关系，则3的补元是 ， 6的补元是 。 3．一个连通平面图G有10条边，G中度为1的结点有2个，其余是度为6的结点，则G中 共有___________个面。 4．一棵树有2个4度结点，3个3度结点，其余结点是树叶，树叶的个数为__________。 5．设图G的邻接矩阵为?0M=?1???11101??0?0??，则G的可达性矩阵为_________。 6．在一棵根树中，有且只有一个结点的入度为___________。 7．命题(a∧b)∨b = b的对偶命题是 。 8．算式的表达式为 (((a+(b÷c))*d)-e)，则此式的波兰符号表示法为 。 四、证明题（每题6分，共12分） 1、无向图G如图所示。（1）证明G是哈密尔图；（2）证明G不是平面图。 2．设是布尔代数，证明对于B中任意元素a,b （1） （2） 浙 江 工 业 大 学 考 试 命 题 纸