湖南大学离散数学考试试卷

诚信应考,考试作弊将带来严重后果！湖南大学课程考试试卷课程名称：离散数学；课程编码：08038试卷编号：A；考试时间：120分钟题号一二三四五六七八九十总分应得分101010151010151010100实得分评卷人特别提示：答案请写答卷纸上，计算题与证明必须有步骤一、填空题(每小题1分,共10分)1、树是连通的，且边的条数等于点数____，去掉任何一条边后树不_____。2、树中度数为1的结点数的下限是_____。3、一棵无向树的结点数是99个，则这树所有点的度数和___4、哈密顿回路是指________________________________________________.。5、存在哈密顿回路的充分条件是___________________________________。6、欧拉回路是指________________________________________________.。7、存在欧拉路但不存在欧拉回路的充要条件________________________。8、给出下图的关联矩阵————————————————。9、根据关联矩阵依次算出上图中各点的入度、出度、度数，并验证是否满足握手定理。考试中心填写：____年___月___日考试用专业班级：学号：姓名：装订线（题目不得超过此线）湖南大学课程考试试卷湖南大学教务处考试中心10、关系R是集合A上的等价关系，那么关系R的_____是集合一个划分，给定义集合A的一个划分，如何构造出集合A上的等价关系__________。二、(10分)黄、李、肖预测德国A、乌拉圭B、西班牙C、荷兰D的名次，黄说“德国冠军，乌拉圭亚军”，李说“荷兰亚军，西班牙第4名”，肖说“德国亚军，乌拉圭第四名”，结果三人预测的结果都只对了一个，请问最后的名次是什么。三、(10分)在自然推理系统中构造下列推理的证明：前提：x(F(x)G(x))结论：xF(x)zG(z)四、(15分)设A={2,3,4,6,8,12,24},R为此集合A上的整除关系。证明R是偏序关系，画出偏序集A,R的关系图、哈斯图、关系矩阵、极大元、极小元，判断是否存在最小元、最大元。五、(10分)什么是包含排斥原理？利用该原理求1到1000之间不能同时被3,5,8整除数的个数，并画出其文氏图，在其中填入各部分的数字以验证。六、(10分)利用真值表求命题公式(pq)(pr)化为主析取范式、主合取范式。七、(15分)在某个特殊通信系统中，A，B，C，D，1，2，3，4，5，6，7，8，9，0共14个字符出现的频率分别为：10,5,3,2,8,9,17,11,12,1,7,6,4,13，请构造相应的最优二叉树即Huffman树，并求出其总权(树顶的数字)，还必须给出构造最优二叉树的过程，最后分别给出这14个字符的Huffman编码。八、（10分）设S={0,1,2,3,4,5,6}，xy=(x+y)mod7，构造其运算表，判断是否存在单位元，判断是否存在零元，判断是否为群？必须给出详细的步骤。九、(10分)什么是生成树？什么是带权图的最小生成树？请用你的语言描述最小生成树的避圈法(Kruskal算法)，并给出下图的最小生成树。