安徽大学2004-2005学年第二学期 《离散数学》期末考试试卷（A卷）
年级 专业 姓名 学号 座
位号
大项 登分
一、单项选择（在备选答案中选出一个正确答案，
得 分 --------------------------------------------------------------------------------------------------------------------------------------------------- 装一 二 三 四 五 六 七 总分 阅卷人 订并将其号码填在题干后的括号内。每题2分，共20分） 1 在自然数集N上，下列哪种运算是可结合的？（ ） A. a*b?a?b B. a*b?max{a,b} C. a*b?a?2b D. a*b?a?b(mod3) 2 下列代数系统
A. S?{0,1,3,5}，*是模7加法 B. S?Q（有理数集合），*是一般乘法
C. S?Z（整数集合），*是一般减法 D. S?{1,3,4,5,9}，*是模11乘法
线
3 若
1
C. n整除m且 m整除n D. n不整除m且 m不整除n 4 下面哪个集合关于指定的运算构成环？（ ） A. {a?b32|a,b?Z}，关于数的加法和乘法 B.{n阶实数矩阵}，关于矩阵的加法和乘法 C. {a?b2|a,b?Z}，关于数的加法和乘法
????ab??a,b?Z?D. ???，关于矩阵的加法和乘法 ?ba???????5 在代数系统中，整环和域的关系为（ ）。 A. 域一定是整环 B.域不一定是整环 C. 整环一定是域 D. 域一定不是整环 b e c a d g f 6 N是自然数集，?是小于等于关系，则(N,?)是（ ）。 A. 有界格 B.有补格 C. 分配格 D. 有补分配格 7 图1-1给出的哈斯图表示的格中哪个元素无补元？（ ）
A. a B. c C. e D. f 图1-1
8 给定下列序列，可构成无向简单图的结点度数序列的是（ ）。
A.（1，1，2，2，3） B.（1，3，4，4，5） C.（0，1，3，3，3） D.（1，1，2，2，2） 9 欧拉回路是（ ）。
A.路径 B.简单回路 C.既是基本回路也是简单回路 D.既非基本回路也非简单回路 10 哈密尔顿回路是（ ）。
A.路径 B.简单回路
2
C.既是基本回路也是简单回路 D.既非基本回路也非简单回路
二、填空题（以下每个下划线为一空，请按要填入合适的内容。每空2分，共30分）。
1 设S是非空有限集，代数系统(P(S),?,?）中，P(S)对?运算的单位元是＿
得
分 求
＿＿＿，零元是＿＿＿＿，P(S)对?运算的单位元是＿＿＿＿。 a b c ? 表2-1 2 在运算表2-1中空白处填入适当符号，使({a,b,c},?)成为群。 a 错误！未找到引用源。 a 错误！未找到引用源。 b a b c 错误！未找到引用源。＿＿＿＿，错误！未找到引用源。＿＿＿＿，错误！未找到引用源。＿＿＿＿，错误！未找到引用源。＿＿＿＿。 3 设H?{0,4,8}，?H,?12?是群?N12,?12?的子群，其中
N12?{0,1,2,???,11}，?12是模12加法，则?N12,?12?有＿＿＿＿
个真子群，H的左陪集3H?＿＿＿＿，4H?＿＿＿＿。 4设?A,?,?,??是一个布尔代数，如果在A上定义二元运算?为：
a?b?(a?b)?(a?b)，则?A,??是一个＿＿＿＿。
5 任何一个具有2n个元素的有限布尔代数都是＿＿＿＿ 6 若连通平面图G有4个结点，3个面，则G有＿＿＿＿条边。 7 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有＿＿＿＿个度数为1的结点。
8 无向图G是由k（k?2）棵数组成的森林，至少要添加＿＿＿＿条边才能使G成为一棵树。
得
分 3
三、求解题（20分）
1 试写出?N6,?6?中每个子群及其相应的左陪集。 （6分）
2 若一个有向图G是欧拉图，它是否一定是强连通的？若一个有向图G是强连通的，它是否一定是欧拉图？说明理由。 （6分） 3 有向图G如图3-1所示。 （1）求G的邻接矩阵A； （2分）
e3
e1 e6 v4
e7 v3
v21 分） （2）G中v1到v4长度为4的路径有几条？ （e4 e2 （3）G中v1到自身长度为3的回路有几条？ （2分） v2 e5 （4）G是哪类连通图？ （2分）
图3-1
四、证明题（30分）
1 设?G,*?是一群，x?G。定义：a?b?a*x*b，
?a,b?G。证明?G,??也是一群。 （10分）
得 分 2 证明：
（1）证明在格中成立：(a*b)?(c*d)?(a?c)*(b?d)。 （5分）
4
（2）证明布尔恒等式：(a*c)?(a?*b)?(b*c)?(a*c)?(a?*b)。 （5分） 3 证明：
（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。 （5分）
（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。
5
