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

华南农业大学期末考试参考答案(A卷)-第一学期考试科目: 离散结构考试类型:(闭卷)考试考试时间: 120 分钟学号姓名年级专业题号一二三四总分得分评阅人考试注意事项:①本试题分为试卷与答卷2部分。试卷有四大题,共6页。②所有解答必须写在答卷上,写在试卷上不得分。得分一、选择题(本大题共25小题,每小题2分,共50分)、计算题:(本大题共5个小题,每题5分,共25分)1、解:2、解:(1)集合的整除偏序关系的哈斯图2364891012(2)集合A没有的最小元与最大元;极小元为2,3;极大元为8,9,10,12。(3)集合的上界为12,下界为2,最小上界12,最大下界2。3、解:首先将各边的权重按小到大排序:1,2,3,4,5,6,7,8,9然后使用避圈法得到如下最小生成树,其总权重为1+2+4+6+8=21V1V2V6V3V5V4124684、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分)1、证明:p®(qÙr)(p®q)Ù(p®r)2、证:(1)自反性:对于任意的(2)对称性:对于任意的(3)传递性:对于任意的3、证明:由于T为非平凡树,则n>1,且任何顶点的度数都大于等于1;设T中m条边,k片树叶(顶点度数为1),则其余n-k个分支点的度数均大于等于2,由握手定理与树的性质(m=n-1)有:,显然k≥2,这说明T至少有两片树叶。