北京工业大学本科生考试试卷-集合与图论-A卷-答案

北京工业大学20162017学年第1学期集合与图论 考试试卷北京工业大学20162017学年第1学期集合与图论考试试卷A卷考试说明： 承诺：本人已学习了北京工业大学考场规则和北京工业大学学生违纪处分条例，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。若有违反，愿接受相应的处分。承诺人： 学号： 班号： 。注：本试卷共 10 大题，共 10 页，满分100分，考试时必须使用卷后附加的统一答题纸和草稿纸。卷 面 成 绩 汇 总 表（阅卷教师填写）题号一二三四五六七八九十总成绩满分得分得 分一、选择题（8分）1、设A=1，2，3，则A上的二元关系有（ C ）个。 A 23 ； B 32 ； C ； D 。2、设集合A=1，2，3，4，5上偏序关系的哈斯图为（A）则子集B=2，3，4的最大元（ ）；最小元（ ）；极大元（ ）；极小元（ ）；上界（ ）；上确界（ ）；下界（ ）；下确界（ ）。A、 无，4，2、3，4，1，1，4，4； B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4； D、无，4，2、3，4，1，1，4，无。3、下图中既不是Euler图，也不是Hamilton图的图是（ B ）4集合A=1, 2, 3, 4, 5, 6, 7, 8上的关系R=|x+y=10且x, yA，则R的性质为（ ） A自反的 B对称的 C传递且对称的 D反自反且传递的得 分二、判断题（8分）1（ F）若、是非空集合A上的传递关系, 则是A上的传递关系。2（F ）设f是A到B的函数, g是B到C的函数，若gf是单射，则f是单射。3.（F ）设正则5叉树的树叶数为17，则分支数为i=34.（ T）如果一个有向图D是欧拉图，则D是强连通图。得 分三、（10分）证明：(AB)-(AB) = (B-A)(A-B)证明：(AB)-(AB) = (AB)(AB)根据De.Morgan定律：(AB) = AB(AB)(AB) = (AB)(AB) 3分将(AB)当作一个整体，利用分配律可知：(AB)(AB) = (AB)A)(AB)B) 5分再次利用分配律：(AB)A)(AB)B) = (AA)(BA)(AB)(BB)= (BA)(AB)() 7分 = (BA)(AB) = (B-A)(A-B) 10分得 分四、（10分）R是A上一个二元关系，证明：若R是A上一个等价关系，则S也是A上的一个等价关系，其中S描述如下：（1） S自反的，由R自反， 3分（2） S对称的 6分（3） S传递的 由（1）、（2）、（3）得；S是等价关系。 10分得 分五、（10分）是从A到B的函数，定义一个函数对任意有证明：若f是A到B的满射，则g是从B到 的单射。证明 ： 3分 7分。 10分得 分六、（12分）求递推关系an4 an14an22n 的通解解）分析：方程右边为特征根： q2（二重根）， 2分特解： An2 2n 4分代入原式：A4A4A 6分展开：An22A(n22n1)2A(n24n4)2 8分整理： 2A待定系数： A 10分通解：B1B2nn2。其中B1、B2为任意常数。 12分得 分七、（10分）用Dijkstra算法求图中起点V1V7的最短路径及路长最短路。 解：采用Dijkstra算法，可解得最短路径为：由V1选择下一个节点V3； 2分计算经过集合V1，V3出发的最短路径节点V5； 4分计算从集合V1，V3，V5出发的下一个最短路径节点V6； 6分计算集合V1，V3，V5出发的下一个最短路径节点V6； 8分计算集合V1，V3，V5，V6出发的下一个最短路径节点V7；所以最短路是： V1-V3-V5-V6-V7 10分得 分八、（12分）在二叉树中1.求带权为2，3，5，7，8的最优二叉树T。（5分）2.求T对应的二元前缀码。（5分）（1）（5分）由Huffman方法,得最佳二叉树为：6分（2）（5分）最佳前缀码为：000，001，01，10，11 12分得 分九、（10分）设G为n阶无向简单图，n5，证明G或中必含圈.反证法. 否则G与的各连通分支都是树. 2分设G与的连通分支分别为G1, G2, , Gs和G1, G2, , Gs. 令ni, mi与 nj, mj 分别为Gi, Gj的顶点数和边数. 4分 于是 7分得n2-5n+4 0解出 1 n 4, 矛盾于n 5. 10分得 分十、（10分）设G是连通的简单的平面图，面数r 5r = 5 (2+m-n) 2分由于d(G)3及握手定理又有 2m 3n