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

1装订线华南农业大学期末考试参考答案（A卷）2013-2014学年第一学期考试科目：离散结构考试类型：（闭卷）考试考试时间：120分钟学号姓名年级专业题号一二三四总分得分评阅人考试注意事项：①本试题分为试卷与答卷2部分。试卷有四大题，共6页。②所有解答必须写在答卷上，写在试卷上不得分。一、选择题（本大题共25小题，每小题2分，共50分）1D2B3C4A5C6C7A8B9B10B11B12A13C14C15C16B17D18D19D20D21A22B23D24C25C二、计算题：（本大题共5个小题，每题5分，共25分）1、解：)),(),(()),(),(()),(),(()),(),((zxGyxFzyxzxzGyxFyxzxzGyxyFxyxyGyxyFx2、解：(1)集合A的整除偏序关系的哈斯图得分得分1.5CM2(2)集合A没有的最小元与最大元;极小元为2,3；极大元为8,9,10,12。(3)集合}6,4,2{B的上界为12，下界为2，最小上界12，最大下界2。3、解：首先将各边的权重按小到大排序：1,2,3,4,5,6,7,8,9然后使用避圈法得到如下最小生成树，其总权重为1+2+4+6+8=214、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分）得分2364891012V1V2V6V3V5V4124683装订线1、证明：p(qr))(rqp)()(rpqp(pq)(pr)2、证：|,,,{dcbaR,,ZZba,,ZZdc}cbda|,,,{dcbaR,,ZZba,,ZZdc}dcba(1)自反性：对于任意的Ayx,Ryxyxyxyx,,,(2)对称性：对于任意的Rvuyx,,,Ryxvuyxvuvuyx,,,(3)传递性：对于任意的Rsryxsryxsrvuvuyx,,,3、证明：由于T为非平凡树，则n1，且任何顶点的度数都大于等于1；设T中m条边，k片树叶(顶点度数为1)，则其余n-k个分支点的度数均大于等于2，由握手定理与树的性质(m=n-1)有：)(2)(22)1(22knkvdnnmi，显然k≥2，这说明T至少有两片树叶。4、R，*是一个含幺半群，即独异点证明：(1)*运算满足封闭性(2)*满足结合律(a*b)*c=2.*4..*)2.(cbacbacbaa*(b*c)(3)有单位元，2因为a*2=aa22.2*a=aa2.2(4)有元素不存在逆元0，所以不是群四、应用题（2选1，两道题都做仅以第一道算分；5分）1、基本原则，构造的二元树（二叉树）存在6片树叶，再根据编码一致原则，如左分支所在的边上用0表示，右分支所在的边用1表示或相反都可以。goodbye的编码根据所构造的二元树对照编写2、构造一个图V,E，顶点表示课程，边表示某两门课程存在学生同时选修的情形得分4则问题转换成图着色问题，因为图中存在最大的四阶完全子图（课程1、2、3、4），所以至少要四种颜色表示，即考试至少要安排在四个不同的时间段