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

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

（时间120分钟）

院/系 专业 姓名 学号

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

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

A.自然数集合；

B.整数集合；

C.有理数集合；

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

A.I ；

B.{2|}k k I ∈；

C.{21|}k k I +∈；

D.{35|,}m n m n I +∈。 3. 设6{0,1,,5}N = ，6+为模6加法，则下列元素是66,N <+>的生成元的是（ ）

A.2；

B.3；

C.4；

D.5。 4. 设>?+<,,F 是整环，则>?+<,,F 不一定是（ ）

A.可交换环；

B.无零因子环；

C.含么环；

D.域。 5. 格不一定具有（ ）

A.交换律；

B.结合律；

C.分配律；

D.吸收律。

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

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 为实数集合，{|01}S x x R x =∈∧≤≤，则在代数,max S <>中，

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

2. 设10+为模10加法，则在10{0,1,,9},<+> 中，元素5的阶为＿ ＿＿，6的阶为＿ ＿＿。

3. 设110{1,2,5,10,11,22,55,110}S =，gcd 和lcm 分别为求最大公约数和最小公倍数运算，

则在布尔代数110,gcd,lcm S <>中，原子的个数为＿ ＿＿，元素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) 求(2)(3)(4),,A A A ，说明从1v 到4v 的长为2,3,4的路径各有几条； (3) 求G 的可达矩阵P ； (4) 求G 的强连通分图。

图1

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

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

1. 证明布尔恒等式：()()()()a b a c b c a b c ''*⊕*⊕*=*⊕。

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

证明：,R <*>为独异点。

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

1-->

n n m ，则图G 是连通图。

4. 设,G <*>是一个群，a G ∈；定义一个映射:f G G →，使得对于x G ?∈有1()f x a x a -=**；

证明：f 是,G <*>的群自同构。

安徽大学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.1n -，(1)/2n n -。

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

1. (1) G 的邻接矩阵0

1110

010

01010

1

0A ?? ?

?= ? ???

； 2分 (2) (2)

0121010100200

1

1A ?? ? ?= ?

???；(3)0222002002020

2

0A ?? ?

?= ?

???；(4)02420202

00400

2

2A ??

?

?= ? ???

； 5分 从1v 到4v 的长为2,3,4的路径的条数分别为1,2,2； 8分

(3) G 的可达矩阵为01110

111

01110

1

1

1P ?? ?

?= ? ???

； 10分 (4) 因00000111

01110

1

1

1T

P P ?? ? ?∧= ? ???

，故G 的强连通分图的结点集为1{}v ，234

{,,}v v v 。 12分

2. 88,N <+>的子群为：8{0},<+>，8{0,2,4,6},<+>，8{0,4},<+>，88,N <+>； 4分

元素5确定的各子群的左陪集对应为：{5}，{1,3,5,7}，{1,5}，8N 。 8分

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

1. ()()()()(())a b a c b c a b a b c ''''*⊕*⊕*=*⊕⊕* 2分

()(())(()())(())a b a b c a b a b a b c ''=*⊕**=*⊕***⊕ 6分 1(())()a b c a b c =**⊕=*⊕。 10分

2. 因R 对+和?运算封闭，故R 对*运算封闭；对,,x y z R ?∈， 2分

xyz yz xz xy z y x z xy y x z xy y x z y x y x z y x ++++++=++++++=?++=)(*)(*)*(, xyz yz xz xy z y x yz z y x yz z y x z y z y x z y x ++++++=++++++=?++=)()(*)*(*

故()()x y z x y z **=**，从而R 上的*运算满足结合律； 6分 因对x R ?∈，x x x x =?++=00*0，x x x x =?++=000*，故0为*运算的么元； 综合以上，*为R 上的可结合的二元运算，且R 关于*运算有么元，所以,R <*>为独异点。 10分

3. 假设G 有(2)k k ≥个连通分图，则因G 为简单无向图，故12

()(1)m n k n k ≤

--+， 4分

因为2k ≥，所以02n k n ≤-≤-，011n k n ≤-+≤-， 8分 所以112

2

()(1)(1)(2)m n k n k n n ≤

--+≤

--，这与12

(1)(2)m n n >

--矛盾！

所以图G 是连通图。 10分

4. 对12,x x G ?∈，若12()()f x f x =，则11

12a x a a x a --**=**，故12x x =，从而f 为单射； 3分

y G ?∈，1

a

y a G -**∈且1

()f a

y a y -**=，因此x G ?∈，使()f x y =，所以f 为满射； 6分

,x y G ?∈，1

11

()()()()()()f x y a x y a a x a a y a f x f y ---*=***=*****=*，故f 为同态； 9分

所以f 是,G <*>的群自同构。 10分