离散数学(下)试卷(A卷)参考答案及评分标准
- 格式：doc
- 大小：192.00 KB
- 文档页数：2
《离散数学（下）》考试试题（A 卷）参考答案及评分标准
一、单选题（每小题2分，共20分）
1. B ；
2. A ；
3. B ；
4. A ；
5. B ；
6. D ；
7. C ；
8. C ；
9. A ；10. C 。
二、判断题（每小题2分，共10分。
对的打√，错的打×）
1. ×；
2. ×；
3. √；
4. ×；
5. √。
三、填空题（每小空2分，共20分）
1. 6；4；3；8a ；
2. 有界格；原子；
3.是；不是；
4. 2；1n -。
四、计算题（每小题10分，共30分）
1. 解：（共10分）
)(b a c b a a '⊕*'*'*'⊕
＝b a a c b a a '*'⊕*'*'*'⊕ (2分) ＝b a a '*'⊕ (6分) ＝b a b a a a '⊕='⊕*'⊕)()( (10分)
最小支配集：{b,f,e}, 最小点覆盖：{b,d,e,f,g,h}, 最小边覆盖：{(a,b),(c,d),(e,j),(f,h),(g,i)}， 最大独立集：{b,e,h,i}， 最大匹配：{(a,b),(c,d),(e,j),(f,h),(g,i)}， 最小点割：{b,f,e}, 最小割集：{(a,b),(a,f),(a,e)}， 点正常着色：{b,e,h,i},{a,c,j},{d,f,g}. 边正常着色：{(a,b),(c,d),(e,j),(f,h),(g,i)}, {(b,c),(d,e),(a,f),(h,j)}, {(a,e),(f,i),(g,j),(c,h)},{(b,g),(d,i)}.
3. 解：
>< ,G 的正规子群有{}>< ,1π、>< ,G 、{}>< ,,21ππ、{}>< ,,31ππ、
{}>< ,,41ππ。
（5分）
{}>< ,1π的商群为{}{}{}{}
{}><*,,,,ππππ，其中*运算表为： （6分） ⎥⎥
⎥
⎥⎥
⎥⎥
⎥⎥
⎥⎥
⎥
⎥⎥⎦
⎤
⎢⎢⎢⎢
⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=1011010000010110100010101001001101000010011010000110000110010100011100001000111000010001110000110011A
>< ,G 的商群为{}<,G
{}>< ,,21ππ的商群为<,,ππ*运算表为： （8分）
{}>< ,,31ππ的商群为< （9分）
{}>< ,,41ππ的商群为< （10分）
五、证明题（每小题10分，共20分）
1. 证： 设ab 的阶等于n ，即()e ab n
=。
(2分)
于是()b ab b n
=，()b b ba n
=。
(5分)
故()e ba n
=，得ba 的阶小于等于n 。
(7分) 即ba 的阶小于等于ab 的阶。
类似可得ab 的阶小于等于ba 的阶。
(9分)
于是ab 的阶等于ba 的阶。
(10分)
2. 证：设T 中有p 个结点，s 个树叶， (2分)
则T 中其余p s -个结点的度数均大于等于2， (4分)
且至少有一个结点的度大于等于k 。
可得： (6分)
1222()2(1)p
i i q p deg v p s k s ==-=≥--++∑，有s k ≥。
(8分)
所以T 中至少有k 个树叶。
(10分)。
