本部_离散数学II_试卷_a_答案

1、 计算机学 院、系2005 /2006 学年（ 1 ）学期期末考试试卷 离散数学II 试卷（A 卷）专业 年级 班级 姓名 学号 题号一二三四五六七八九十总分得分一、单选题 (在每小题的四个备选答案中，选出一个最正确的答案，并将答案的序号填在题干的括号内。每小题2分，共24分)1、由r棵树组成的森林的顶点数n与边数m有下列关系（ B ）。An=m-rBn=m+rCn=m-1Dm+n+r=02、若无向图G中不含孤立点，且存在一条经过所有边的闭路径，则（B）。AG必为哈密顿图BG必为欧拉图CG必为不连通图DG必为简单图3、下图是（ C ）。 A强连通B单侧连通C弱连通D不连通4、以下是简单图的度序

2、列的是（ C ）。A(5,4,3,2,2,2,1)B(7,6,5,4,4,3,1)C(6,43,3,3,2,1)D(6,6,4,3,2,2,1)5、下列无向图中，不是哈密顿图的是（ B ）。6、满足下列条件（ A ）的无向图不一定是树。A边数=顶点数-1B任意一对结点间有且仅有一条通路C连通且无回路D无回路，但添加任何一条边后必产生唯一回路7、设为一代数系统，S=e,a,b。*运算定义如下。则（ D ）为其子代数。*eabebbeaebabbeeABCD8、以下代数系统中，群是（ D ）。*abcd*abcdaabcdaabcdbbeacbbbbbccdbaccbadddaebddbcaAB*

3、abcd*abcdaabcdabadcbbadcbabcdccdcacdcabddcbadcdbaCD9、设为一代数系统，aS，则（ A ）。A 若a存在逆元，则其逆元未必唯一B 若中存在幺元，则幺元未必唯一C 若中既有幺元又有零元，则幺元、零元必不相等D 若a既有左逆元，又有右逆元，则左、右逆元必相等10、为两个代数系统，且存在S到S1的同态映射h，则（ B ）。A 若中存在幺元，则也存在幺元B 若中存在幺元，则未必存在幺元C 若中每个元素存在逆元，则中每个元素存在逆元D 若中满足结合律，则中*也满足结合律11、下列代数系统中，不构成群的是（ C ）A S=1,3，*是模4的乘法BS是有理数

4、集，*是普通加法CS是实数集，*是普通乘法DS是整数集，*是普通加法12、设是群，为其子群，则（ B ）。AaH，a在H中的逆元与a在G中的逆元未必相等BaH，a在H中的逆元与a在G中的逆元一定相等C中的幺元与中的幺元未必相等D中必存在零元，且与中的零元相等二、填空题（除特别说明外，每空2分，共33分）1、设简单图G共有10个顶点，其中，8个顶点的度数为3，其余4个顶点的度数都小于3，则G至多有 14 条边。2m83+222、树T有5个2度结点，4个3度结点，3个4度结点，其余都是树叶，则T的树叶有 12 个。m=n-1=5+4+3+x-1, 2m=52+43+34+x3、为了从（n,m）连通

5、图中得到一棵最小生成树，必须删除G的 m-(n-1) 条边。4、20阶完全图的关联矩阵共有 380 个1，30阶有向完全图的邻接矩阵共有 900 个1。20192=190，1902=380；3030=9005、下图的一条欧拉闭路径为 abdfecdebca 。 6、设是一代数系统，R为S之上的一个二元关系。如果R是等价关系且对于p,q,r,tS有pRq且rRt蕴涵(p*r)R(q*t)，则称R是上的同余关系。7、设为群，群的幺元为e。对任意aG，则称满足ar=e的最小正整数r 为元素a的阶。群中任意元素的阶 |G|。8、(2分)设是群，对a,bG，填写以下计算过程中每一步的理由(a*b)*(b

6、-1*a-1) =a*(b*b-1)*(a-1) *满足结合律 =e逆元定义、幺元定义9、(5分)设是环（是阿贝尔群，是半群，对+满足分配律），0是环的加法幺元、乘法零元。对a,bR，-a表示a的加法逆元。填写以下证明过程每步的理由。(-a)b=(-a)b+(ab+(-(ab) 逆元定义ab+(-(ab)=0, 幺元定义(-a)b+0=(-a)b =(-a)b+ab)+(-(ab) +满足结合律 =(-a)+a)b+(-(ab) 对满足分配律 =0b+(-(ab) (-a)+a0 =-(ab) 0b=0,0+(-(ab)=(-(ab)10、设为群，为其子群，利用可定义G上的一个右陪集关系（等价

7、关系）=|ab当且仅当a、b在H的同一个左（右）陪集中/a,bG,a*b-1H。a关于H的右陪集Ha= h*a|hH，其性质为|Ha| |H|。三、计算题（共35分）1、（11分）对下列有向图 （1）（2分）该图是否有关联矩阵表示？如果有，写出关联矩阵；如果没有，说明为什么没有？回答1：没有。因为关联矩阵无法表示边的方向，无法表示环。回答2（其他课本有）：有，用1和-1表示边的方向。（2）（4分）写出该图的邻接矩阵；写出（不需计算）路径矩阵和可达矩阵；A= 1 1 1 0B= 1 1 1 1P=B 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 0 0 1 0 1（

8、3）（3分）求出v1到v4的长度为3的拟路径条数，要求写出计算过程；计算A、A2、A3，取A31行4列元素A2=1 1 2 2A3=1 3 3 3 0 1 0 00 0 0 1 0 1 1 1 0 1 1 2 0 0 0 1 0 1 0 0v1到v4的长度为3的拟路径条数为3条（4）（2分）如何通过邻接矩阵计算判断有向图是否强连通？简单阐述判断过程。通过邻接矩阵计算出可达矩阵，判断可达矩阵是否全1。2、（每小题3分，共6分）按要求画图：（1）画出5个结点的所有不同构的树；3棵，度序列分别为(4,1,1,1,1)(3,2,1,1,1)(2,2,2,1,1)。每棵1分；多了同构的树扣1分；多了不是

9、树的图扣1分。（2）画出算术表达式a*3+5/(b-c)+7的二元树表示。3分。运算符做分支结点、操作数做叶子结点、有序树（左右儿子有序）1分；运算符计算次序正确1分；树完整1分。3、（8分）设S=a,b,c,d,e，S上的运算*运算表如下：*abcdeaaaaaabaecbdcacbcddabcdeeadded（1）（1分）*是否有零元？a（2）（1分）*是否有幺元？d（3）（5分）每个元素是否有逆元？写出各个元素的所有逆元。a无逆元，b逆元为e，c逆元为e，d逆元为d，e逆元为b,c,e（4）（1分）*是否满足交换律？是4、（10分）S= a,b,c,d，构造群，并使c为幺元。（1） （2分）完成*的运算表； *abcdabdacbdcbacabcddcadb（2） （4分）写出各个元素的逆元和阶；a、d互为逆元,c逆元是自己，b逆元是自己。a、d的阶是4，b的阶是2（3） （2分）找出的所有子群；3个c,c,b,c,a,b,d（4） （2分）该群是否是循环群？若不是，说明理由；若是，找出所有的生成元。是，生成元可以是a或d四、证明题（8分）设是一群，是其子群。求证：若AB=G，则必有A=G或B=G。证明：（反证法