离散数学II模拟卷答案.docVIP

计算机学 院、系期末考试模拟卷 专业 年级 班级 姓名 学号 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 一、单选题 (在每小题的四个备选答案中，选出一个最正确的答案，并将答案的序号填在题干的括号内。每小题2分，共24分) 1、从哈密尔顿图中删除一条边后，所得的图（ B ）不连通的。 A．一定是 B．绝对不是 C．可能是 2、下列无向简单图中是欧拉图的是（ D ）。 3、(n,m)简单连通图的生成树有（ A ）条边。 A．n-1 B．m-1 C．n-m+1 D．m-n+1 4、一个连通带权无向图的最小生成树（ B ），其各边权重之和（ B ）。 A．唯一……唯一 B．不一定唯一……唯一 C．唯一……不一定唯一 D．不一定唯一……不一定唯一 5、下图不是（ C ）。 A．无向图 B．连通图 C．完全图 D．正则图 6、设集合S＝{1,2,3,......,10}，以下定义的*使S,*不是代数系统的是（ C ）。 A．x*y=max(x,y) B．x*y=min(x,y) C．x*y=LCM(x,y)，即x,y的最小公倍数 D．x*y=GCD(x,y)，即x,y的最大公约数 7、关于特殊元，以下说法正确是（ D ）。 代数结构中的幺元与零元总不相等 一代数系统中关于一个二元运算可能有2个左幺元和2个右幺元 代数系统中一定存在一个元素它既是左零元又是右零元 一个代数系统关于一个二元运算的零元必唯一 8、代数系统S,*中的*满足交换律，有幺元e，其子代数为A,*，则（ D ）。 A．A,*不一定满足交换律 B．e一定是A,*中的幺元 C．A,*中一定有幺元，幺元不一定是e D．A,*不一定有幺元 9、2个代数系统S,*、S1,(，除了情况（ A ），其余情况下 S,*的性质（运算律、特殊元、逆元）可传递到S1,(中。 A．S,*到S1,(存在单一同态 B．S,*到S1,(存在满同态 C．S,*与S1,(同构 D．S1,(是S,*的商代数 10、在自然数集N上，下列定义的*运算满足结合律的是（ B ）。 A．a*b=a-b B．a*b=max(a,b) C．a*b=a+2b D．a*b=|a-b| 11、以下代数系统G,*不构成群的是（ B ）。 A．G={1,10}，*是模11数乘 B．G={3,4,5,9}，*是模11数乘 C．G=Q（有理数），*是数加 D．G=Z（整数），*是数加 12、N16,+16的子群阶数不可能是（ C ）。 A．1 B．2 C．3 D．4 二、填空题（除特别说明外，每空2分，共33分） 1、以下有向图中，包含a的强分图的顶点集是 {a,b,f} ，包含a的单向分图的顶点集是 {a,b,c,f}，包含a的弱分图的顶点集是 {a,b,c,e,f} 。 2、20个顶点的无向连通图的生成树，其关联矩阵共有 38 个1，其邻接矩阵共有 38 个1。 3、3个顶点的互不同构的树有 1 棵，3个顶点的完全二元树有 1 棵。 4、下图的一条哈密顿回路为 gabcdefg 。 5、代数系统A,*，A={a,b,c}，*的定义如下： * a b c a a a c b a b c c c c c 则*的零元为 c ，幺元为 b ，无逆元的元素有 2 个。 6、设S,*与S’,*’是代数结构，*、*’是二元运算。如果 存在h:S→S’使得(a,b∈S, h(a*b)=h(a)*’h(b)则称S,*到S’,*’存在同态。 7、（5分）?群G,*中，幺元是e，对a∈G，ai=as(i≤s)，下列序列证明as-i=e，在空格出填上证明理由。 ai=as*as-i 群幂运算性质 ai=ai*as-i a-i*ai= a-i*(ai*as-i) 每个元素存在逆元 a-i*ai= (a-i*ai)*as-i 结合律 e=e*as-i 逆元定义 e=as-i 幺元定义 8、群N6,+6，子群H={0,3}，左陪集4H= {4,1} ，所有左陪集构成的集合为 {{0,3},{1,4},{2,5}} 。 三、应用题（共35分） 1、（14分）对下列有向图 （1）（2分