安徽大学-计算机学院-2006-级-2007—2008-学年-第-二-学期《离散数学》(下)试卷(A卷)及参考答案A

安徽大学2007— 2008学年第 2 学期 《离散数学（下）》考试试卷（A卷）

一、单项选择题（每小题2分，共20分）

1. 下列集合关于数的加法和乘法运算不能构成环的是（ ）

A.自然数集合； B.整数集合； C.有理数集合； D.实数集合。 2. 设I为整数集合，则下列集合关于数的加法运算不能构成独异点的是（ ）

A.I； B.{2k|k?I}； C.{2k?1|k?I}； D.{3m?5n|m,n?I}。 3. 设N6?{0,1,L,5}，?6为模6加法，则下列元素是?N6,?6?的生成元的是（ ）

A.2； B.3； C.4； D.5。 4. 设?F,?,??是整环，则?F,?,??不一定是（ ）

A.可交换环； B.无零因子环； C.含么环； D.域。 5. 格不一定具有（ ）

A.交换律； B.结合律； C.分配律； D.吸收律。

6. 设S?{1,2,4,8}，o和?分别表示求最小公倍数和最大公约数运算，则?S,o,??是（ ）

A.有补格； B.分配格； C.有补分配格； D.布尔代数。

7. 一个含4个结点的无向图中有3个结点的度数分别为1,2,3，则第4个结点的度数不可能是（ A.0； B.1； C.2； D.4。

8. 设连通的简单平面图G中有10条边和5个面，则G的结点数为（ ）

A.6； B.7； C.8； D.9。

9. 设无向树T中有1个结点度数为2，2个结点度数为3，3个结点度数为4，则T中的树叶数为（ A.10； B.11； C.12； D.13。

10.设G为连通的无向图，若G仅有2个结点的度数是奇数，则G一定具有（ ）

A、欧拉路径； B、欧拉回路； C、哈密尔顿路径； D、哈密尔顿回路。

二、填空题（每小空2分，共20分）

1. 设R为实数集合，S?{x|x?R?0?x?1}，则在代数?S,max>中，

S关于max运算的么元是＿ ＿＿，零元是＿ ＿＿。

2. 设?10为模10加法，则在?{0,1,L,9},?10?中，元素5的阶为＿ ＿＿，6的阶为＿ ＿＿。3. 设S110?{1,2,5,10,11,22,55,110}，gcd和lcm分别为求最大公约数和最小公倍数运算， 则在布尔代数?S110,gcd,lcm?中，原子的个数为＿ ＿＿，元素22的补元为＿ ＿＿。

）

）

4. 在格?L,?,??中，?a,b?L，a?b当且仅当a?b?＿ ＿＿当且仅当a?b?＿ ＿＿。 5. 一个具有n个结点的简单连通无向图的边数至少为＿ ＿＿，至多为＿ ＿＿。

三、解答题（第1小题12分，第2小题8分，共20分）

1. 设图G如图1所示， (1) 求G的邻接矩阵A； (2) 求A,A,A(2)(3)(4)，说明从v1到v4的长为2,3,4的路径各有几条；

(3) 求G的可达矩阵P； (4) 求G的强连通分图。

图1

2. 求群?N8,?8?的所有子群及由元素5确定的各子群的左陪集，其中N8?{0,1,???,7}，?8是模8加法。

四、证明题（每小题10分，共40分）

1. 证明布尔恒等式：(a?b)?(a??c)?(b??c)?(a?b)?c。

2. 设R为实数集合，?和?为数的加法和乘法运算，对?a,b?R，a*b?a?b?a?b，

证明：?R,??为独异点。

3. 证明：若(n,m)简单无向图G满足m?

4. 设?G,??是一个群，a?G；定义一个映射f:G?G，使得对于?x?G有f(x)?a?x?a；

证明：f是?G,??的群自同构。

?11(n?1)(n?2)，则图G是连通图。 2安徽大学20 07 —20 08 学年第 2 学期

《离散数学（下）》（A卷）考试试题参考答案及评分标准

一、单项选择题（每小题2分，共20分）

1.A； 2.C； 3.D； 4.D； 5.C； 6.B； 7.B； 8.B； 9.A； 10.A。

二、填空题（每小空2分，共20分）

1.0，1； 2.2，5； 3.3，5； 4.a，b； 5.n?1，n(n?1)/2。

三、解答题（第1小题12分，第2小题8分，共20分）

??0111?1. (1) G的邻接矩阵A??0010????0101?； 2?0010????0121??222?242?(2) A(2)??0101???0020????；A(3)??0??0202???0020?0202?；A(4)??0?0040?； 5?0101????0020????0202??从v1到v4的长为2,3,4的路径的条数分别为1,2,2； 8??0111?(3) G的可达矩阵为P??0111????0111?； 10?0111????0000?(4) 因P?PT??0111????0111?，故G的强连通分图的结点集为{v1}，{v2,v3,v4}。 12?0111??

2. ?N8,?8?的子群为：?{0},?8?，?{0,2,4,6},?8?，?{0,4},?8?，?N8,?8?； 4元素5确定的各子群的左陪集对应为：{5}，{1,3,5,7}，{1,5}，N8。 8

分 分

分

分

分 分

分