l离散数学期末考试卷1_A答案

一、单选题（20小题，每小题2分，共40分） 1、D 11、 B 2、A 12、 B 3、B 4、D 13、 A 5、B 14、 D 6、A 15、 C 7、C 16、 C 8、C 17、 B 9、C 18、 A 10、A 19、 B 20、 D 二、填空题（20小题，每空1分，共20分） 1、 4, 5, 6 10、 0 2、IA 11、 d 3、 12、 14 4、{0, {0}, {{0}}, {0, {0})} 13、 (PAr Q) V (r PAQ) 14、 10 5、(Vx)(G(x) — F(x)) a -,(Vx)(F(x) — G(x)) 15、 既是单射又是满射 或(Vx)(G(x) T F(x)) a (3y)(F(y) a「G(y)) 16、 反自反性、反对称性和传递性 6、A 17、 P — Q 7、(Vx)(H(x) — N(x)) △」(Vx)(N(x) T H(x)) 18、 或(Vx)(H(x) T N(x)) a (3y)(N(y) a「H(y)) 19、 出度为0的结点 8、6 9、a 20、 {〈 {①，{①}},①),〈{①，{①}}，{①}〉} 三、简答题（4小题，每小题6分，共24分） 1、解： 1）邻接矩阵为： 0 110 2) A2 = 2 1 0 0 0 1 1 0 （2分） 1 1 1 0 3 3 ,（2 分） 1 1 由、到％长度为2的路有1条, 由、到％长度为4的路有3条。（1分） 3） G = （y,E）的可达性矩阵为 1 1 1 r 1 1 1 1 1 1 1 1 0 0 0 1 P （1分） 2、 （根据树的完整程度酌情减分） 3、答: 子集 上确界 下确界 {a,b,c} a d {c,d,e} c 无 A a 无 4、解：该问题相当于求图的最小生成树问题，此图的最小生成树为: D 第2页共3页 （4分） 因此如图铺设煤气管道所需费用最小，最小费用为： W（r）= 2 + 2 + 2 + 2 + 2 + 2 + 2+3 + 3+4+1=25 （万元）.（2 分） 四、证明题（2小题，每小题8分，共16分） 1、证明:①假设存在 ,，使得 f （） = /（）,则 m + n _u + v,男|3 么淅=i/且 ” =v , 由 jh 匕得>= , 即/ 是入身寸。 2222 (3分) ②任取