离散数学(本)2016年3月份试题.doc

离散数学（本）2016年3月份试题一、单项选择题（每小题3分，本题共15分）1设A=1, 3, 5, 7，B=2, 4, 6，A到B的关系R= | y=x+3，则R为 ( )A. , , B. , C. , , D. , , , 2若集合Aa, b, c，则下列表述不正确的是( ) A A BaA CaA Da, b, cA 3设A（x）：x是学生，B（x）：x是大学生，则命题“不是所有的学生都是大学生”可符号化为（ ）A($x)(A(x)B(x) B(x)(A(x)B(x) C($x)(A(x)B(x) D(x)(A(x) B(x) 4设G为连通无向图，则（ ）时，G中存在欧拉回路AG不存在奇数度数的结点 BG存在偶数度数的结点 CG存在一个奇数度数的结点 DG存在两个奇数度数的结点5n阶无向完全图Kn的边数是（ ） A. n(n-1), B. n(n-1)/2 C. n-1 D. n(n-1)二、填空题（每小题3分，本题共15分）6设集合A=1, 2, 3，B=2, 3, 4，C=3, 4, 5，则A(C-B )等于 7设A=a, b，B=1, 2，C=a, b，从A到B的函数f=, ，从B到C的函数g=, ，则g f等于 8对于任意的无向图，其所有结点的度数之和等于该图的边数的 9设G是具有n个结点m条边k个面的连通平面图，则n+k -2等于 10设个体域D1, 2, 3, 4，A(x)为“x等于4”，则谓词公式($x)A(x)真值为 三、逻辑公式翻译（每小题6分，本题共12分） 11将语句“如果小王来学校，则他会参加比赛”翻译成命题公式 12将语句“今天天晴，昨天下雨”翻译成命题公式 四、判断说明题（判断各题正误，并说明理由每小题7分，本题共14分）13设A=1，2，3 ，R=, ，, ，则R是等价关系14(x)P(x)Q(y)R(x)中量词的辖域为P(x)Q(y) 五计算题（每小题12分，本题共36分）15设集合A=a, b, c，B=a, b , b，试计算（1）AB； （2）A - B； （3）AB16设G=，V=v1, v2, v3, v4, v5，E=(v1,v3) , (v1,v5) , (v2,v3) , (v3,v4) , (v4,v5) ，试（1）给出G的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形17试利用Kruskal算法求出如下所示赋权图中的最小生成树（要求写出求解步骤），并求此最小生成树的权ooooov6v1v2v5v3ov416245793152 六、证明题（本题共8分）18试证明：(PQ)R （QR） P离散数学（本）2016年3月份试题参考解答一、单项选择题（每小题3分，本题共15分）1B 2C 3D 4A 5B二、填空题（每小题3分，本题共15分）61, 2, 3, 57, 8两倍9m10真（或T，或1）三、逻辑公式翻译（每小题6分，本题共12分）11设P：小王来学校， Q：他会参加比赛 （2分） 则命题公式为： P Q （6分）12设P：今天天晴， Q：昨天下雨 （2分）则命题公式为：PQ （6分）四、判断说明题（每小题7分，本题共14分）13错误 （3分）R不是等价关系，因R中不包含，故不满足自反性 （7分）14错误 （3分）辖域为紧接与量词之后的最小子公式P(x) （7分）五计算题（每小题12分，本题共36分）15解：（1）AB= b； （4分）（2）A - B= a, c； （8分）（3）AB=, , , , , (12分）16解：（1）G的图形表示如图一所示： （3分） 图一（2）邻接矩阵： （6分）（3）v1，v2，v3，v4，v5结点的度数依次为2，1，3，2，2 （9分）（4）补图如图二所示： （12分） 图二17解：用Kruskal算法求产生的最小生成树。步骤为： w(v2,v6) =1，选(v2,v6)w(v4,v5) =1，选(v4,v5)w(v1,v6) =2，选(v1,v6)w(v3,v5) =2，选(v3,v5) w(v2,v3) =4，选(v2,v3) （6分）52ooooov6v1v2v5v3ov4162457931最小生成树如图三所示： （9分） 图三最小生成树的权w(T)=1+1+2+2+4=10 （12分）六、证明题（本题共8分）18证明： （1）(PQ) P （1分）（2）PQ T（1）E （3分）（3）（QR） P （4分）（4）R P （5分）（5）Q T（3）（4）I