交大 离散 期末考卷lisanab答案【DOC精选】.docVIP

上 海 交 通 大 学 试 卷（ AB 卷答案） A一 选择题（50’，每题2’, 在错误答案上划\，在题号上写得分。） D B B A D C D C D B C D B A A B D A B A D B A D A B五 选择题（50’，每题2’） B D D C B A B A B B A B B C A B D C D C B D D B D A二 B六 填空题（30’，每题2’, 在错误答案上划\，在题号上写得分。） 1-100的这100个整数中，能被2,3,5之一整除的数有_______74__________个。 设，则 含个结点的简单图共有 个。 设A = {1, 2, 3, …., 13, 14, 15}, 定义R={x,y|x(y(mod 4),x,y(A}， 则[2]=_ __ {2,6,10,14}______________ 5． 设A和B都是有穷非空集合，A和B的基数为n, 则A到B有_____ __n!________种不同的双射。 6．关系的定义域和值域分别为， 7．设为实数集上的函数，， 则_____x+6 __________ 下图的一条欧拉回路是_(e1,e2,e3,e4,e7,e5,e6,e8)_或点的序列 或点边序列。 设图G=（V,E）有7个结点，其中6个结点的度都为3，一个结点的度为6， 则该图有 12 条边。 有向图G的关联矩阵为， 则其邻接矩阵为： 11．下面两个有向图的同构映射为 f(v1)=b,f(v2)=a,f(v3)=c,f(v4)=e,f(v5)=d,f(v6)=f 。 12．一棵树有个结点的度为1，个结点的度为2，…，个结点的度为k-1，结点最大的度为k。问度为k的结点有 个。 某简单平面图有8个结点，18条边，则每个域的边数是 3 。 在K3，K4，K5，K6，K型图)中，非平面图为 K5，K6，K型图 。 对于权序列，构造Huffman树，则带权路径总长为 34 。 A三B三．(5) 对任意的集合A，证明 证明: 空集是任意集合的子集。 (3’) (1’) 由上面两式知：。 (1’) A四B二．(5) 设是非空集合A上的二元关系，是自反的、传递的，试证： 证明：若，所以存在，使得 ， 又因为是传递的，所以可以得到。 (2’) 若，因为是自反的，所以有，于是得到 由此即知。 （3’） 所以由, 可知。 A五B一．(5)下图中直线的交点都为图的结点，共有18个结点。 判断图中是否存在欧拉回路，若有，则写出一条欧拉回路，否则说明理由。 判断图中是否存在哈密顿回路，若有，则写出一条哈密顿回路，否则说明理由。 判断该图是否为可平面图。 答: (1’)不存在欧拉回路, (1’)因为无向连通图存在欧拉回路的充要条件是各结点的度都是偶数,而此图中结点1度为3. (1’)存在哈密顿回路： (1’) 1－2－5－8－11－7－14－15－16－12－9－13－17－18－10－4－6－3－1。 (1’)是可平面图 A六B四．(5)G为简单平面图（域的个数，结点个数，边的个数，连通支个数），其对偶图的域有个。求证：（1） （2） 证明：(2’) (1) n-m+d=k+1 n*-m*+d*=2 n*=d m*=m d*=l 因为对偶图的域有个，所以 （1*） (3’) (2) 因为G为简单平面图且，所以 （2*） 又由欧拉公式的推广形式 （3*） 由（1*），（3*）得（消去n，k） (4*) （2*）代入（4*）得（消去m） = = A 卷 总 8 页 第 页