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、VxGx Fx a -,VxFx Gx 15、 既是单射又是满射 或VxGx T Fx a 3yFy a「Gy 16、 反自反性、反对称性和传递性 6、A 17、 P Q 7、VxHx Nx △」VxNx T Hx 18、 或VxHx T Nx a 3yNy a「Hy 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 23 34125 （万元）.（2 分） 四、证明题（2小题，每小题8分，共16分） 1、证明①假设存在 m,n,u,v ，使得 f （ m,n ） /（ u,v ）,则 m n _u v,男|3 么淅i/且 ” v , 由 jh 匕得〃,□ , 即/是入身寸。 2222 3分 ②任取 n,v〉eRxR , 均有 x,y u v,u-v RxR , 使得 / X，V W V u - VU V- V 3,从而/是满射。（3分） （2分） 综合①②知/是双射。 2、该命题符号化为VxQx / a 3xQx aZx3x7x aZx 2 分 证1 3xQxaZxP 6 Za T2I （1分） ⑵ Qa a ZaES 1 （1 分）（7） Ra T4,5 I （1分） ⑶ VxQx t / P 8 Ra a Z T6,7 I （1分） ⑷ Qa T Ra US 3 （1 分）（9） 3x7x a Zx EG8 （1分） 5 Qa T2I