国开大学2021年01月1009《离散数学(本)》期末考试参考答案.docx

1、座位号 19试卷代号：1009国 家 开 放 大 学 2 0 2 0 年 秋 季 学 期 期 末 统 一 考 试离散数学(本) 试题2021年1月题 号二三四总 分分 数得 分评卷人一、单项选择题(每小题4分，本题共20分)1.若集合A=a,b,c,d, 则下列表述正确的是( ).A. a A B.a AC. a,b,cCA D. a,b,c,d A2.设集合A=1,2,3,4,5,6,B=1,2,3,A 到B 的关系R= |xA,yB且x=y, 则 R=( ).B. ,D. ,3.已知无向图G 的结点度数之和为10,则G 图的边数为( ),A.10 B.20C.5 D.304.设 G 是连通

2、平面图，v,e,r 分别表示G 的结点数、边数和面数，则v,e 和r 满足关系式( )A.v-e+r=2 B.v+e+r=2C.v-e-r=2 D.e-v+r=25.设 A(x);x 是人，B(x):x 是学生，则命题“不是所有人都是学生”可符号化为( ).A.(3x)(A(x)A B(x)B.(Vx)(A(x)A B(x)C.(3x)(A(x)AB(x)D.(Vx)(A(x)B(x)得 分评卷人二、判断题(每小题4分，本题共20分)三、逻辑公式翻译(每小题6分，本题共12分)6.设集合A=1,2,B=2,3,C=3,4, 则 AUB-C=1,2.( )A. 正确 B. 错误7.如果R 和R

3、是 A 上的自反关系，则RR 是自反的. ( )A. 正确 B. 错误8.设集合A=a,b,c,B=1,2,3, 作 f:AB, 则不同的函数个数为9. ( )A. 正确 B. 错误9.两个图同构的必要条件是结点数相等、边数相等、度数相同的结点数相等。( )A. 正确 B. 错误10.设个体域D=1,2,3,4,A(x) 为“x 等于3”,则谓词公式(3x)A(x) 的真值为 F.( )A. 正确 B. 错误得 分评卷人11.将语句“他上午去教室上课，下午去体育馆参加比赛. ”翻译成命题公式.12.将语句“如果他接受了这个任务，他一定能完成的. ”翻译成命题公式.评卷人得 分四、计算题(每小题

4、12分，本题共48分)13.设集合A=1,2,3,A 上的关系R=|x A,y A且x+y4,S=|x A,y A 且xy, 试求R,S,R,s(S).14.设G=,V=vj,v,v,E=(v,v),(v,v),(v,v), 试：(1)给出G 的图形表示；(2)求出每个结点的度数；(3)画出其补图的图形，2015. 设 图G=, 其中，结点集V=a,b,c,d,e, 边集 E=(a,c),(a,e),(b,d),(b,e),(c,e),(d,e), 对应边的权值依次为2、3、3、4、1及5,试：(1)画出G 的图形；(2)求出G 权最小的生成树及其权值.16.设谓词公式(3x)(A(x,y)A

5、(Vz)B(x,y,x)A(Vy)C(y,x), 试 ：(1)写出量词的辖域；(2)指出该公式的自由变元和约束变元.21试卷代号：1009国 家 开 放 大 学 2 0 2 0 年 秋 季 学 期 期 末 统 一 考 试离散数学(本) 试题答案及评分标准22(供参考)一 、单项选择题(每小题4分，本题共20分)1.C 2.B 3.C 4.A二、判断题(每小题4分，本题共20分)6.A 7.A 8.B 9.A三、逻辑公式翻译(每小题6分，本题共12分)11.设 P: 他上午去教室上课，Q: 他下午去体育馆参加比赛.则命题公式为：PA Q12.设 P: 他接受了这个任务，Q: 他一定能完成这个任务

6、， 则命题公式为：PQ.四、计算题(每小题12分，本题共48分)13.R=,S=,R- =,s(S)=,14. (1)G 的图形表示如图一所示：图一(2)deg(vi)=1,deg(v)=1,deg(v)=3,deg(v)=12021年1月5.D10.B(2分) (6分) (2分) (6分)(3分) (6分) (9分) (12 分 )(4分)(8分)(3)补图如图二所示：图二(12分)15. (1)G 的图形如图三所示：b(4分)图三用 Kruskal 算法求最小生成树的步骤为：23w(c,e)=1, w(a,c)=2, w(b,d)=3, w(b,e)=4,选(c,e)选(a,c)选(b,d)选(b,e)最小生成树如图四所示：为 图四(9分) (12分)(2分) (4分) (6分) (9 分 ) 中的y. (12分)最小生成树的权C(T)=1+2+3+4=10.注：用破圈法求最小生成树参照评分。16.(1)3x 量词的辖域为A(x,y)A(Vz)B(x,y,x),Vz 量词的辖域为B(x,y,z),Vy 量词的辖域为C(y,z).(2)自由变元为A(x,y)A(Vx)B(x,y,z) 约束变元为A(x,y)A(Vz)B(x,y,x)中的y, 以及C(y,x) 中 的z.中的x 与 B(x,y,x) 中的x, 以及C(y,z)