安徽大学 离散数学 04-05a

《安徽大学 离散数学 04-05a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、----------------------装---------------------------------------------订----------------------------------------线----------------------------------------安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）年级专业姓名学号座位号大项一二三四五六七总分阅卷人登分得分一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每题2分，共20分）1在自然数集上，下列哪种运算是可结

2、合的？（）A.B.C.D.2下列代数系统<，*>中，哪个是群？（）A.，*是模7加法B.（有理数集合），*是一般乘法C.（整数集合），*是一般减法D.，*是模11乘法3若<，*>是<，*>的真子群，且，，则有（）。A.整除B.整除C.整除且整除D.不整除且不整除4下面哪个集合关于指定的运算构成环？（）A.，关于数的加法和乘法abcdefgB.阶实数矩阵，关于矩阵的加法和乘法C.，关于数的加法和乘法D.，关于矩阵的加法和乘法5在代数系统中，整环和域的关系为（）。A.域一定是整环B.域不一定是整环C.整环一定是域D.域一定不是整环6是自然数集，是小于等于

3、关系，则是（）。A.有界格B.有补格C.分配格D.有补分配格7图1-1给出的哈斯图表示的格中哪个元素无补元？（）A.B.C.D.图1-18给定下列序列，可构成无向简单图的结点度数序列的是（）。A.（1，1，2，2，3）B.（1，3，4，4，5）C.（0，1，3，3，3）9学生答题注意：勿超黑线两端；注意字迹工整。10D.（1，1，2，2，2）9欧拉回路是（）。A.路径B.简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路10哈密尔顿回路是（）。A.路径B.简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路得分二、填空题（以

4、下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）。1设是非空有限集，代数系统中，对运算的单位元是＿＿＿＿，零元是＿＿＿＿，对运算的单位元是＿＿＿＿。表2-1abca①a②babcc③c④2在运算表2-1中空白处填入适当符号，使成为群。①＿＿＿＿，②＿＿＿＿，③＿＿＿＿，④＿＿＿＿。3设，是群的子群，其中，是模12加法，则有＿＿＿＿个真子群，的左陪集＿＿＿＿，＿＿＿＿。4设是一个布尔代数，如果在上定义二元运算为：，则是一个＿＿＿＿。5任何一个具有个元素的有限布尔代数都是＿＿＿＿。6若连通平面图有4个结点，3个面，则有＿＿＿＿条边。7一棵

5、树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿＿＿个度数为1的结点。8无向图是由（）棵数组成的森林，至少要添加＿＿＿＿条边才能使成为一棵树。得分三、求解题（20分）1试写出中每个子群及其相应的左陪集。（6分）2若一个有向图是欧拉图，它是否一定是强连通的？若一个有向图是强连通的，它是否一定是欧拉图？说明理由。（6分）3有向图如图3-1所示。（1）求的邻接矩阵；（2分）（2）中到长度为4的路径有几条？（2分）（3）中到自身长度为3的回路有几条？（2分）27441231365（4）是哪类连通图？（2分）图3-19学生答题注意：勿超黑线两

6、端；注意字迹工整。10得分四、证明题（30分）1设是一群，。定义：，。证明也是一群。（10分）2证明：（1）证明在格中成立：。（5分）（2）证明布尔恒等式：。（5分）3证明：（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。（5分）（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。（5分）9学生答题注意：勿超黑线两端；注意字迹工整。10安徽大学2004-2005学年第二学期《离散数学》期末考试试卷（A卷）参考答案一、单项选择1．B;2.D;3.A;4.C;5.A;6.C;7.B;8.D;9.B;10.C.二、填空题

7、1，，；2，，，；35，，；4交换群；5同构；65；79；8。三、求解题1解：子群有：，，。的左陪集为：，，，，，的左陪集为：，，的左陪集为：，2答：（1）一个有向欧拉图一定是强连通图。因为是欧拉图，存在欧拉回路，中的每个结点至少在中出现一次。因而中任意两点，都在中，相互可达，故是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。3解：（1）（2）由中可知，到长度为4的路径有条（56748，，，）。（3）由中可知，到自身长度为3的回路有1条（）。（4）是单向连通图。四、证明题1证明：显然是上的二元运算（即满

8、足封闭性），要证是群，需证结合律成立，同时有单位元，每个元素有逆元。，有运算是可结合的。9学生答题注意：勿超