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

《华南农业大学 离散结构 期末考试 2013试卷答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、装订线华南农业大学期末考试参考答案（A卷）2013-2014学年第一学期　考试科目：　离散结构　　考试类型：（闭卷）考试　　　考试时间：　120　分钟学号姓名年级专业题号一二三四总分得分评阅人考试注意事项：①本试题分为试卷与答卷2部分。试卷有四大题，共6页。②所有解答必须写在答卷上，写在试卷上不得分。得分一、选择题（本大题共25小题，每小题2分，共50分）1D2B3C4A5C6C7A8B9B10B11B12A13C14C15C16B17D18D19D20D21A22B23D24C25C得分1.5CM二、计算题：（本大题共5个小题，每题5分，共25分）1、解：2、解：(

2、1)集合的整除偏序关系的哈斯图3装订线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得分三、证明题：

3、（本大题共4个小题，每题5分，共20分）1、证明：p®(qÙr)3装订线(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至少有两片树叶。4、是一个含幺半群，即独异点证明：得分(1)*运算满足封闭性(2)*满足结合律(a*b)*c=a*(b*c)(3)有单位元，2因为a*2=2*a=(4)有元素不存在逆

4、元0，所以不是群四、应用题（2选1，两道题都做仅以第一道算分；5分）1、基本原则，构造的二元树（二叉树）存在6片树叶，再根据编码一致原则，如左分支所在的边上用0表示，右分支所在的边用1表示或相反都可以。goodbye的编码根据所构造的二元树对照编写2、构造一个图，顶点表示课程，边表示某两门课程存在学生同时选修的情形3装订线则问题转换成图着色问题，因为图中存在最大的四阶完全子图（课程1、2、3、4），所以至少要四种颜色表示，即考试至少要安排在四个不同的时间段3