《离散数学》期末考试卷05-06(2)
- 格式：doc
- 大小：178.50 KB
- 文档页数：3
安徽大学2005-2006学年第二学期
《离散数学》期末考试试卷（A 卷）
一、选择题（每小题2分，共20分）
1．在自然数集N 上，下列运算中可结合的是（ ） A ．b a b a -=* B ．},max{
*b a b a = C ．b a b a 2*+= D ．b a b a -=*
2．二元运算*有两个左零元，则*一定（ ）
A ．满足结合律
B ．满足交换律
C ．不满足结合律
D ．不满足交换律
3．设><,*A 是二元代数系统，元素A a ∈有左逆元1-l a 和右逆元1-r a ，若运算
*满足（ ）律，则11--=r l a a 。
A ．结合
B ．交换
C ．等幂
D ．分配
4．下列代数><,*S 中，（ ）是群。
A ．}5,3,,1,0{=S ，*是模7加法
B ．Q S =（有理数集），*是普通乘法
C ．Z S =（整数集合），*是一般减法
D ．}9,5,4,3,1{=S ，*是模11乘法
5．群>+<1212,N 总共有（ ）子群。
A ．4
B ．6
C ．8
D ．12
6．下面（ ）集合关于指定的运算构成环。
A ．},|}2{3Z b a b a ∈+，关于数的加法和乘法
B ．n {阶实数矩阵}，关于矩阵的加法和乘法
C ．},|}2{Z b a b a ∈+，关于数的加法和乘法
D ．⎪⎭
⎪⎬⎫⎪⎩⎪⎨⎧∈⎪⎪⎭⎫ ⎝⎛Z b a a b b a ,，关于矩阵的加法和乘法
7．N 是自然数集，≤是小于等于关系，则≤><,N 是（ ）
A ．有界格
B ．有补格
C ．分配格
D ．有补分配格
8．在布尔格>⊕<1,0,',,*,B 中有3个原子1a ,2a ,3a ，则='1a （ ）
A ．32*a a
B ．32a a ⊕
C ．'3'2*a a
D ．'3
'2a a ⊕ 9．含有5个结点、3条边的不同构的简单图有（ ）
A ．2个
B ．3个
C ．4个
D ．5个
10．一个无向图有4个结点，其中3个度数为2,3,3，则第4个结点度数不可能是（ ）
A ．0
B ．1
C ．2
D ．4
二、填空题（每空2分，共20分）
1．设>⨯<,G 为非零实数乘法群，G G f →:是同态映射，x
x f 1)(=，则=)(G f ________，=)(f Ker ________。
2.设}8,4,0{=H ，>+<12,H 是群>+<1212,N 的子群，其中
}11,...,2,1,0{12=N ，12+是模12加法，则>+<1212,N 有________个真子群，H 的左培集=H 3____________，=H 4____________。
3．在有界分配格中，具有补元的元素集合组成一个＿__＿＿_格。
4．n 为________数时，无向完全图n K 是欧拉图；=n ________时，无向完全
图n K 仅存在欧拉路径而不存在欧拉回路。
5．一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为
________。
6．无向图G 是有k （2≥k ）棵树组成的森林，至少要添加_______条边才能
使G 成为一棵树。
三、综合题（每小题10分，共60分）
1．设><,*G 是一个群，证明：对于G 中任意的d c b a ,,,,1111,,,d c b a ，如果11**c a c a =，11**d a d a =，11**c b c b =。
则有11**d b d b =。
2．设><,*A 和>< ,B 是两个群。
><,*A 和>< ,B 的笛卡尔积是代数系统>⊗⨯<,B A ，其中⊗是一个二元运算，使得对B A ⨯中的任意><11,b a 和
><22,b a ，
有>>=<<⊗><21212211,*,,b b a a b a b a 。
证明：>⊗⨯<,B A 也是一个群。
3．设><,*G 是一个群。
令,|{G a a H ∈=且对一切G b ∈，有}**a b b a =。
证明：H 是一个正规子群。
4．设≤><,L 为一个格，试证明：≤><,L 为分配格的充要条件是对于任意的L c b a ∈,,，有)*(*)(c b a c b a ⊕≤⊕。
5．下列是布尔代数>⊕<1,0,',},*,,,1,0{b a 上的布尔表达式，试求出它们的主析取范式和主合取范式：
(1))*())(*(),(y x y x b y x f ⊕⊕=。
(2))*()**(),,(z b y x a z y x f ⊕=。
6．证明
(1)设G 是具有n 个结点的无向简单图，其边数2)2)(1(2
1+--=n n m 。
试证明G 是哈密尔顿图。
(2)设简单平面图G 中结点数7=n ，边数15=m ，证明：G 是连通的。
