国家开放大学2021年（202101-202107）《1009离散数学（本）》期末考试真题及答案完整版（共2套）

试卷代号：1009国家开放大学2020年秋季学期期末统一考试离散数学（本）试题2021年1月一、单项选择题（每小题4分，本题共20分）1.若集合A={a，b，c，d}，则下列表述正确的是(). A.{a}∈A B.a∉A C.{a,b,c)⊂A D.{a，b,c,d}∈A2.设集合A={l，2，3，4，5，6），B={1，2，3)，A到B的关系R={<x，y>|x∈A，y∈B且x=y2}，则R=(). A.{<1,l>,<2,4>) B.(<l,1>,<4,2>) C.{<1,1>,<6,3>) D.{<1,1>,<2,1>)3.已知无向图G的结点度数之和为10，则G图的边数为(). A.10 B.20 C.5 D.304.设G是连通平面图，v，e，r分别表示G的结点数、边数和面数，则v，e和r满足关系式() A.v-e+r=2 B.v+e+r=2 C.v-e-r=2 D.e-v+r=25.设A(x)：x是人，B(x)：x是学生，则命题“不是所有人都是学生”可符号化为(). A.¬(∃x)(A(x))∧B(x)) B.(∀x)(A(x))∧B( C.¬(∃x)(A(x))∧¬B(x)) D.¬(∀x)(A(x))→B二、判断题（每小题4分，本题共20分）6.设集合A={l，2），B={2，3)，C={3，4)，则A∪B-C=｛1，2}.() A.正确 B.错误7.如果R1和R2是A上的自反关系，则R1∩R2是自反的.() A.正确 B.错误8.设集合A={a，b，c），B={1，2，3）,作f：A→B，则不同的函数个数为9.() A.正确 B错误9.两个图同构的必要条件是结点数相等、边数相等、度数相同的结点数相等.() A.正确 B.错误10.设个体域D={1，2，3，4)，A（x)为“x等于3”，则谓词公式(∃x)A(x）的真值为F. A.正确 B.错误三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“他上午去教室上课，下午去体育馆参加比赛，”翻译成命题公式. 12.将语句“如果他接受了这个任务，他一定能完成的.”翻译成命题公式.四、计算题（每小题12分.本题共48分） 13.设集合A={1，2，3），A上的关系R={<x，y>|x∈A，y∈A且x+y>4}，S={<x，y>|x∈A，y∈A且x<y}，试求R，S，R-1，s(S). 14.设G=<V,E>,V={v1,v2,v3,v4），E={（v1,v3），(v2,v3),(v3,v4)}，试： (1)给出G的图形表示； (2)求出每个结点的度数； (3)画出其补图的图形. 15.设图G=<V，E>，其中，结点集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，试： (l)画出G的图形； (2)求出G权最小的生成树及其权值. 16.设谓词公式（∃x）(A(x，y)∧(∀x)B(∀z))∧(∀y)C(y，z (1)写出量词的辖域； (2)指出该公式的自由变元和约束变元.试卷代号：1009国家开放大学2021年春季学期期末统一考试离散数学（本）试题2021年7月一、单项选择题（每小题4分，本题共20分）1.若集合A={1，2，3，4}，则下列表述不正确的是(). A.{2,3}∈A B.A⊆{1,2,3,4} C.2∈A D.{2,3}⊂A2.设A={1，2}，B={1，2，3，4，5}，A到B的关系R={<x，y>|x∈A,y∈B且x+1=y}，则R=(). A.｛<1，2>｝ B.｛<1,1>,<1,2>,<1,3>,<1,4>,<1,5>｝ C.{<1，1>，<2，1>} D.｛<1，2>，<2，3>)3.设G是欧拉图，则G的奇数度数的结点数为()个. A.O B.1 C.2 D.44.无向图G是棵树，边数是12,则G的结点度数之和是(). A.12 B.13 C.24 D.65.设A(x)：x是水果，B(x)：x是草莓，则命题“不是所有的水果都是草莓”可符号化为(). A.(∀x)(A(x)⋀B(x)) B.¬(∃x)(A(x)⋀B C.¬(∃x)(A(x)⋀¬B(x)) D.¬(∀x)(A(x二、判断题（每小题4分，本题共20分）6.设A={1，2}，B={a，b，c}，作f:A→B，则共有6个不同的函数。() A.正确 B.错误7.边数相等与度数相同的结点数相等是两个图同构的必要条件.() A.正确 B.错误8.设G是具有扎个结点m条边五个面的连通平面图，则n-m=2-k.() A.正确 B.错误9.不存在集合A与B，使得A∈B与A⊆B同时成立.() A.正确 B.错误10.设个体域D={1，2}，则谓词公式(∀x)P(x)∨（∃x）Q(x)消去量词后的等值式为(P(1)∧P(2))∨(Q(1)∨ A.正确 B.错误三、逻辑公式翻译（每小题6分，本题共12分） 11.将语句“我会英语，并且会德语.”翻译成命题公式， 12.将语句“如果明天下雨，我们就去图书馆。”翻译成命题公式，四、计算题（每小题12分，本题共48分） 13.设集合A={{a}，a，b}，B={a，{b})，试计算 (1)A∩B;(2)A∪B;(3)A-(A∩B) 14.设偏序集<A，R>的哈斯图如下，B为A的子集，其中B={b，c}，试 (1)写出R的关系表达式； (2)画出关系R的关系图； (3)求出B的最大元、极大元、上界， 15.图G=<V，E>，其中V={a，b，c，d}，E={（a，b），(a，c)，(a，d)，(b，c)，(c，d)}，对应边的权值依次为6、5、2、3及8，试 (1)画出G的图形； (2)写出G的邻接矩阵； (3)求出G权最小的生成树及其权值. 16.求P→(Q∧R)的合取范式与主析取范式.试卷代号:1009国家开放大学2020年秋季学期期末统一考试离散数学(本)试题答案及评分标准(供参考)2021年1月一、单项选择题(每小题4分,本题共20分) 1.C 2.B 3.C 4.A 5.D二、判断题(每小题4分,本题共20分) 6.A 7.A 8.B 9.A 10.B三、逻辑公式翻译(每小题6分,本题共12分)11.设P:他上午去教室上课,Q:他下午去体育馆参加比赛.(2分)则命题公式为:P∧Q(6分)12.设P:他接受了这个任务,Q:他一定能完成这个任务,(2分)则命题公式为:P→Q.(6分)四、计算题(每小题12分,本题共48分)13.R={<2,3>,<3,2>,<3,3>}(3分)S={<1,2>,<1,3>,<2,3>}(6分)R-1={<2,3>,<3,2>,<3,3>}(9分)s(S)={<1,2>,<1,3>,<2,3>,<2,1>,<3,1>,<3,2>}(12分)14.(1)G的图形表示如图一所示:图一(4分)(2)dg(v1)=1,deg(v2)=1,deg(v3)=3,deg(v4)=1(8分)(3)补图如图二所示:图二(12分)15.(1)G的图形如图三所示:图三用Kruskal算法求最小生成树的步骤为:w(c,e)=选(c,e)w(a,c)=选(a,c)w(b,d)=3,选(b,d)w(b,e)=4,选(b,e)最小生成树如图四所示:图四(9分)最小生成树的权C(T)=1+2+3+4=10.(12分)注:用破圈法求最小生成树参照评分。(1).∃x量词的辖域为A(x,y)∧(∀z)B(x,y,z),(2分)∀z量词的辖域为B(x,y,z),(4分)∀y量词的辖域为C(x,z)(6分)(2)自由变元为A(x,y)∧(∀z)B(x,y,z)中的y,以及C(y,z)中的z.(9分)约束变元为A(x,y)∧(∀z)B(x,y,z)中的x与B(x,y,z)中的z,以及C(y,z)中的y.(12分)试卷代号：1009国家开放大学2021年春季学期期末统一考试离散数学（本）试题答案及评分标准（供参考）2021年7月一、单项选择题（每小题4分，本题共20分）1.A2.D3.A4.C5.D二、判断题（每小题4分，本题共20分）6.B7.A8.A9.B10.A三、逻辑公式翻译（每小题6分，本题共12分）11.设P:我会英语，Q:我会德语. （2分）则命题公式为：P∧Q. （6分）12.设P:明天下雨，Q:我们就去图书馆. （2分）则命题公式为：P→Q. （6分）四、计算题（每小题12分，本题共48分）13.解：(1)A∩B={a}(2)A∪B={{a}，a(3)A-(A∩B)一{14.解：(1)R<b，(2)关系图 （8分）(3)集合B无最大元，极大元为b与c、无上界 （12分）15.解：(1)G的图形表示