离散数学（本）2020年7月份试题.docx

《离散数学（本）2020年7月份试题.docx》由会员分享，可在线阅读，更多相关《离散数学（本）2020年7月份试题.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学（本）2020年7月份试题离散数学（本）2017年7月份试题 一、单项选择题（每小题3分，本题共15分） 1设A=1, 3, 5, 7, 9，B=2, 4, 6，A到B的关系R=<x, y>|x-y=1，则R= ( ) A<1, 2>, <2, 3>, <3, 4> B<1, 2>, <3, 4>, <5, 6> C<1, 1>, <2, 2>, <3, 6> D<3, 2>, <5, 4>, <7, 6> 2若集合Aa, b, c

2、，则下列表述正确的是( ) Aa, b A BaA Ca, bA DA 3设个体域为集合1，2，3，4，5，则公式(“x)($y)(x+y=5)的说明可为 ( ) A存在一整数x有整数y满意x+y=5 B对任一整数x存在整数y满意x+y=5 C存在一整数x对随意整数y满意x+y=5 D任一整数x对随意整数y满意x+y=5 4设G为连通无向图，则（ ）时，G中存在欧拉回路 AG存在两个奇数度数的结点 BG存在一个奇数度数的结点 CG不存在奇数度数的结点 DG存在偶数度数的结点 5n阶无向完全图Kn的边数及每个结点的度数分别是（ ） An(n-1)与n Bn(n-1)/2与n-1 Cn-1与n D

3、n(n-1)与n-1 二、填空题（每小题3分，本题共15分） 6设集合A=1, 2, 3，B=2, 3，C=3, 4，则A(B-C) = 7设A=a，b，B=1，2，C=a，b，从A到B的函数f=<a，1>, <b，2>，从B到C的函数g=<1，b>, <2，a >，则g f等于 8设G=<V，E>是一个图，| E |=10，则G的结点度数之和为 9设G是具有n个结点m条边k个面的连通平面图，则n+k -2 = 10设个体域D1, 2, 3，A(x)为“x的2倍大于2”，则谓词公式（“x）A(x)的真值为 三、逻辑公式翻译（每小题6分

4、，本题共12分） 11将语句“假如他驾驭了计算机的用法，那么他就能完成这项工作”翻译成命题公式 12将语句“前天下雨，昨天还是下雨”翻译成命题公式 四、推断说明题（推断各题正误，并说明理由每小题7分，本题共14分） 13设A= a，b，c ，R=< a，a >, < b，b >, < c，c > ，< a，b >，< b，a >，< b，c >，< c，b >，则R是等价关系 14(“x)(P(x)Q(y)R(x)中量词“的辖域为(P(x)Q(y) 五计算题（每小题12分，本题共36分） 15设集合A=a, b

5、, c, d ，B=a, b，试计算 （1）AB； （2）A - B； （3）AB 16设G=<V，E>，V=v1, v2, v3, v4，E=(v1,v2) , (v1,v3) , (v1,v4) , (v2,v3) , (v3,v4)，试 （1）给出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形 17试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权 六、证明题（本题共8分） 18试证明：PQ P (P Q) 离散数学（本）2017年7月份试题 参考解答 一、单项选择题（每小题3分，本题

6、共15分） 1D 2A 3B 4C 5B 二、填空题（每小题3分，本题共15分） 61, 2, 3 7<a，b >, <b，a > 820（或：2|E|） 9m 10假（或F，或0） 三、逻辑公式翻译（每小题6分，本题共12分） 11设P：他驾驭了计算机的用法， Q：他能完成这项工作 （2分） 则命题公式为： P Q （6分） 12设P：前天下雨， Q：昨天还是下雨 （2分） 则命题公式为：PQ （6分） 四、推断说明题（每小题7分，本题共14分） 13错误 （3分） R不是等价关系，因R中包含< a，b >与< b，c >，但不包含< a

7、，c >，故不满意传递性 （7分） 14错误 （3分） 辖域为紧接量词“之后的最小子公式(P(x)Q(y)R(x) （7分） 五计算题（每小题12分，本题共36分） 15（1）AB= a, b, c, d； （4分） （2）A - B= c, d； （8分） （3）AB=<a, a>, <a, b>, <b, a>, <b, b>, <c, a>, < c, b >, <d, a>, < d, b > （12分） v1 o o o o v2 v3 v4 图一 16（1）G的图形表示如图一所示：

8、 （3分） （2）邻接矩阵： （6分） （3） deg(v1)=3， deg(v2)=2， deg(v3)=3， deg(v4)=2 （9分） v1 o o o o v2 v3 v4 图二 （4）补图如图二所示： （12分） 17 用Kruskal算法求产生的最小生成树。步骤为： w(v1,v7) =1， 选e1=v1v7 w(v3,v4) =3， 选e2=v3v4 w(v2,v7) =4， 选e3=v2v7 w(v3,v7) =9， 选e4=v3v7 w(v4,v5) =18，选e5=v4v5 w(v1,v6) =22，选e6=v1v6 （6分） 最小生成树如图三所示： （9分） 图三 最小生成树的权C(T)= 1+3+4+9+18+22=57 （12分） 六、证明题（本题共8分） 18证明： （1）PQ P （1分） （2）P P（附加前提） （2分） （3）Q T（1）（2）I （4分） （4）PQ T（2）（3）I （5分） （5） (PQ) T（4）E （6分） （6） (P Q) T（5）E （7分） （7）P (P Q) CP规则 （8分） 说明：因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最终得出结论得2或1分 另，可以用真值表验证