华南农业大学 离散结构 期末考试 2013试卷答案

1.5CM

华南农业大学期末考试参考答案（A卷）

2013-2014学年第 一 学期 考试科目： 离散结构 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业

题号 一 二 三 四 总分 得分 评阅人 考试注意事项： ①本试题分为试卷与答卷2部分。试卷有四大题，共6页。 ②所有解答必须写在答卷上，写在试卷上不得分。

得分 一、选择题（本大题共 25 小题，每小题 2 分，共 50 分）

1 D 2 B 3 C 4 A 5 C 6 C 7 A 8 B 9 B 10 B 11 B 12 A 13 C 14 C 15 C 16 B 17 D 18 D 19 D 20 D 21 A 22 B 23 D 24 C 25 C

二、计算题：（本大题共 5 个小题，每题 5 分，共 25 分） 得分 1、解：

?x(?yF(x,y)??yG(x,y))??x(?yF(x,y)??zG(x,z))??x?y(F(x,y)??zG(x,z))??x?y?z(F(x,y)?G(x,z))

2、解：(1) 集合A的整除偏序关系的哈斯图

8 12 10 4 6 9 2 3

(2)集合A没有的最小元与最大元; 极小元为2,3；极大元为8,9,10,12。 (3)集合B?{2,4,6}的上界为12，下界为2，最小上界12，最大下界2。

3、解：首先将各边的权重按小到大排序：1,2,3,4,5,6,7,8,9

然后使用避圈法得到如下最小生成树，其总权重为1+2+4+6+8=21

V2 1 V1 2 V6 4 6 V3 8 V4 V5

4、

5、解：以下几种情况： （1）四个不同名次:4!=24

（2）三个不同名次:3！4！/2!/2!=36 （3）两个不同名次:4+6+4=14 （4）同一个名次：1 一共24+36+14+1=75

三、证明题：（本大题共 4 个小题，每题 5 分，共 20 分）

得分 2

装订线

1、证明：p? (q?r) ??p?(q?r)?(?p?q)?(?p?r)

?(p? q) ?(p? r)

2、证：

R?{??a,b?,?c,d?? | ?a,b??Z??Z?, ?c,d??Z??Z?, a?d?b?c} R?{??a,b?,?c,d?? | ?a,b??Z??Z?, ?c,d??Z??Z?, a?b?c?d} (1)自反性：对于任意的?x,y??A

x?y?x?y???x,y?,?x,y???R

(2)对称性：对于任意的??x,y?,?u,v???R

?x?y?u?v?u?v?x?y???u,v?,?x,y???R

(3)传递性：对于任意的

?x?y?u?v?u?v?r?s?x?y?r?s???x,y?,?r,s???R

3、证明：由于T为非平凡树，则n>1，且任何顶点的度数都大于等于1；设T中m条边，

k片树叶(顶点度数为1)，则其余n-k个分支点的度数均大于等于2，由握手定理与树的性质(m=n-1)有：

2m?2(n?1)?2n?2??d(vi)?k?2(n?k)，

显然k≥2，这说明T至少有两片树叶。

4、是一个含幺半群，即独异点

证明：

(1) *运算满足封闭性

(2)*满足结合律

得分 (a*b)*c=(a.b2)*c?a.b.c4?a*b.c2?a*(b*c)

(3)有单位元，2

因为 a*2=a.22.a2?a 2*a=2?a

(4)有元素不存在逆元 0，所以不是群

四、应用题（2选1，两道题都做仅以第一道算分；5分）

1、基本原则，构造的二元树（二叉树）存在6片树叶，再根据编码一致原则，如左分支所在的边上用0表示，右分支所在的边用1表示或相反都可以。 good bye 的编码根据所构造的二元树对照编写

2、构造一个图，顶点表示课程，边表示某两门课程存在学生同时选修的情形

3

则问题转换成图着色问题，因为图中存在最

大的四阶完全子图（课程1、2、3、4），所以至少要四种颜色表示，即考试至少要安排在四个不同的时间段

4