1、绝密绎启用前2022 年 4 月高等教育自学考试全国统一命题考试离离散散数数学学试试题题答答案案及及评评分分参参考考(课程代码摇 02324)一、单项选择题:本大题共 15 小题,每小题 1 分,共 15 分。1. C2. A3. C4. B5. D6. B7. B8. D9. A10. C11. B12. C13. B14. A15. D二、填空题:本大题共 10 小题,每小题 2 分,共 20 分。16. ,17. 1,2,3,4,2,3,418. ,19. 1220. F,T21. 6,422. 3,523. 准,A24. 1025. 2n-k三、计算题:本大题共 5 小题,每小题 6
2、分,共 30 分。26. 解:分别列出两个命题公式的真值表如下P Q RP寅QR寅Q(P寅Q)夷(R寅Q)P遗RP遗R寅Q0 0 0111010 0 1100100 1 0111010 1 1111111 0 0010101 0 1000101 1 0111111 1 111111(1 分)(1 分)(1 分)(1 分)(1 分)从真值表可见,(P寅Q)夷(R寅Q)与 P遗R寅Q 的真值完全相同,因此有(P寅Q)夷(R寅Q)圳P遗R寅Q(1 分)27. 解:(P寅迱 Q)寅R圳迱 (迱 P遗迱 Q)遗R(1 分)圳(P夷Q)遗R(1 分)离散数学试题答案及评分参考 第 1 页(共 3 页)圳(
3、P遗R)夷(Q遗R)(1 分)圳(P遗Q遗R)夷(P遗迱 Q遗R)夷(迱 P遗Q遗R)(1 分)圳M0夷M2夷M4(1 分)圳m1遗m3遗m5遗m6遗m7(1 分)此即所求命题公式(P寅迱 Q)寅R 的主析取范式。28. 解:根据所列关系性质,填表如下摇 摇 摇 摇 运算性质摇 摇 摇 摇x+yx-yxy可结合性是否是可交换性是否是(每空 1 分)29. 解:设度数为 1 的结点数为 n1,由握手定理可得n1+2n2+3n3+knk=2(n1+n2+n3+nk-1)(4 分)解此方程得 n1=2+n3+2n4+(k-2)nk(2 分)30. 解:(1)由题 30 图所示有向图 D,可得其邻接矩
4、阵为MD=0摇 1摇 0摇 01摇 0摇 1摇 01摇 0摇 1摇 11摇 0摇 1摇 0(2 分)(2)由上述 MD,利用矩阵乘法可得M2D=1摇 0摇 1摇 01摇 1摇 1摇 12摇 1摇 2摇 11摇 1摇 1摇 1摇 摇 M3D=1摇 1摇 1摇 13摇 1摇 3摇 14摇 2摇 4摇 23摇 1摇 3摇 1摇 摇(2 分)由此可知,D 中顶点 v3到顶点 v1之间长度为 3 的通路有 4 条。(2 分)四、证明题:本大题共 3 小题,每小题 7 分,共 21 分。31. 证明:坌x,x沂P(A)疑P(B)圳(x沂P(A)夷(x沂P(B)(1 分)圳(x哿A)夷(x哿B)(2 分)圳
5、x哿A疑B(1 分)圳x沂P(A疑B)(2 分)由此可知,P(A)疑P(B)= P(A疑B)。(1 分)离散数学试题答案及评分参考 第 2 页(共 3 页)32. 证明:应用量词辖域扩张等值式可得坌x(P(x)寅坌y(Q(y)寅L(x,y)圳坌x坌y(P(x)寅(Q(y)寅L(x,y)(1 分)圳坌x坌y(迱 P(x)遗(迱 Q(y)遗L(x,y)(2 分)圳坌x坌y(迱 P(x)遗迱 Q(y)遗L(x,y)(1 分)圳坌x坌y(迱 (P(x)夷Q(y)遗L(x,y)(2 分)圳坌x坌y(P(x)夷Q(y)寅L(x,y)(1 分)33. 证明:设 n 阶图 G 中的结点为 v1,v2,vn,易
6、知n啄(G)臆移ni=1d(vi)臆n驻(G)摇 摇 (1)(2 分)而由握手定理移ni=1d(vi)= 2m摇 摇 摇 摇 摇 摇 摇 摇 (2)(2 分)将(2)代入(1),于是得n啄(G)臆2m臆n驻(G)(2 分)从而得到啄(G)臆2m/ n臆驻(G)(1 分)五、综合应用题:本大题共 2 小题,每小题 7 分,共 14 分。34. 解:(1)一颗树的边有 n-1 条,而每条边连接两个结点,故邻接矩阵 M(G)中值为1 的元素个数为 2(n-1)。(4 分)(2)一颗树中任意两个结点都是连通的,因此 MG+M2G+M3G+MnG中值为 0 的元素个数为 0。(3 分)35. 解:(1)A 的幂集P(A)= 准,a,b,c,a,b,b,c,a,c,a,b,c(3 分)(2)偏序关系P(A)-准,哿的哈斯图如答 35 图所示。答 35 图(2 分)由答35 图可见,该偏序关系的极大元为 A=a,b,c,极小元为a,b,c。(2 分)离散数学试题答案及评分参考 第 3 页(共 3 页)
