1、国家开放大学电大本科离散数学2022-2023期末试题及答案（试卷号：1009)一、 单项选择题（每小题3分， 本题共15分）1. 若集合A=1,2,3，则下列表述正确的是(). A. ,2,3EAC. 1,2,3竺AB. ACl,2D. l,2EA2. 设A= (l.2,3), B = (l,2,3,4,A到B的关系R=I.xEA,yEB，工y),则R=() .A. ,B. (,c.,)D. ,3. 无向图G的边数是10，则图G的结点度数之和为（） A. 10c.304. 如图一所示，以下说法正确的是（A. e是割点B. 位，e)是点割集C. b,e)是点割集D. d)是点割集5. 设个体域
2、为整数集，则公式V工3y(x+y=2)的解释可为（） A. 任意整数工，对任意整数y满足工y=2B.对任意整数工，存在整数y满足工y=2c.存在一整数工，对任意整数y满足工y=2D. 存在一整数工，有整数y满足工y2B. 20D. 5、丿b d图一答案：J.C2. D3. B4. A5. B二、 填空题（每小题3分 本题共15分）6. 设集合A= (1,2,3,B = (2,3,4,C= (3,4,5，则BUA -C)等于7. 设A= (1,2,B = 2,3,C= 3,4)，从A到B的函数f=,，从B到C的函数g=,，则Ran(g寸）等于8. 两个图同构的必要条件包括结点数相等、边数相等与9
3、. 设G是连通平面图，v,e,r分别表示G的结点数， 边数和面数，v 值为5,e 值为4则r的值为10. 设个体域D=l.2,3,4)，则谓词公式(3心A（工）消去量词后的等值式为答案：6. 1,2,3,47. 3,4度数相同的结点数相等9. l10. A(l) VA(2) VA(3) VA(4)三、 逻辑公式翻译（每小题6分， 本题共12分）11. 将语句“昨天下雨， 今天仍然下雨， “翻译成命题公式12将语句“若不下雨， 我们就去参加比赛， “翻译成命题公式答案：11. 设P：昨天下雨，Q:今天下雨（2分）则命题公式为：p /Q.(6分）12. 设P:下雨，Q：我们去参加比赛（2分）则命题
4、公式为尸、P-Q.（或飞-P)(6分）四、 判断说明题（判断各题正误， 并说明理由， 每小题7分 本题共14分）13.若图G是一个欧拉图，则图G 中存在欧拉路14. 无向图G的结点数比边数多1，则G是树答案：13. 正确因为若图G是一个欧拉图，则图中存在欧拉回路按定义知，欧拉回路也是欧拉路14. 错误反例：如图G的结点数比边数多1，但不是树乙五、 计算题（每小题12分， 本题共36分）15. 设集合A=l,Z,3,4)上的关系：R= ,),S=,), 试计算(l)RS1(2)R-; (3)rRns). (3分）(5分）(7分）(3分）16. 图G=，其 中V= a, b, c, d), E =
5、 (a, b), (a, c), (a, d), (b, c), (b,d),(c,d)），对应边的权值依次为1、1、5、2、3 及4，请画出G的图形、写出G的邻接矩阵井求出G权朵小的生成树及其权值17. 求勹(PVQ)VR的析取范式与主合取范式答案：15. (l)A UB= (a,b,c,d;(2)A-B=c,d; (4分）(8分）(3)A XB=,(12分）16. (I)G的图形表示如图一所示：VI I;? 图一(2)邻接矩阵：-0 1 1 1 0 l0 lI O ll O l 0(3)deg(v1)=3, deg(v2) =2, deg(v,) =3, deg(v,)=2 (4)补图如图
6、二所示：10v图二17.用Kruskal算法求产生的最小生成树步骤为：心（v,v,)=l，选e,=v,v,w(v.,v,)=3，选e2=v,v,w(v1,v,)=4选e3=v,v, 心(Vs,v,)=9，选e,=v,v, w(v,v,)=18，选es=v.Vsw(v,v,)=22，选e,=v,v,V4 (3分）(6分）(9分）V2 (12分）(6分）最小生成树如出三所示：. IH ,I) 图三最小生成树的权C(T) = I +3+4 +9+ 18+22=57.六、 证明题（本题共8分）18. 设A,B,C均为任意集合，试证明：An(B-C)（AnB)一(AnC)答案：18. 证明：设工EA则x,工EAXA, 因AXA=BXB，故x,:,;EBXB，则有rEB,因此A巨B.设xEB，则x，工EBXB,因AXA=BXB，故r,.rEAXA，则有工EA，因此B竺A.故得A=B.(9分）(12分）(l分）(3分）(5分）(6分）(7分）(8分）
