国家开放大学电大《离散数学(本)》期末题库及答案

1、最新国家开放大学电大离散数学(本)期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并旦每年都在更新。该题库 对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查 找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有其他网 核及教学考一体化答案，敬请查看。离散数学题库及答案一一、单项选择题(每小题3分，本题共15分)1. 若集合 a=a, b9 b= a, b, ( a, b ),则().a. acib,且b. aebf但力芯c. a(zb9 但 awbd. 旦zab2. 集合z=1, 2

2、, 3, 4, 5, 6, 7, 8上的关系夫=5 y>|x+y=10且x, ,则&的性质为().a.自反的b.对称的c.传递旦对称的d.反自反且传递的3. 如果r和人2是z上的自反关系，则r1ur2, rqr2,中自反关系有()个.a. 0b. 2c. 1d. 34. 如图一所示，以下说法正确的是()a.但,时是割边b. («, e)是边割集c. 时0,现是边割集d. (<e)是边割集图一5. 设n (x)： x是人，b (x)： x是学生，则命题“不是所有人都是学生”可符号化为().a. ( v x)(4(a) a5(x)b. (3x)(24(x)ab(x)c

3、 n (vx)(?l(x) fg(x)d. - (3x)(x)a-| 5(x)二、填空题(每小题3分，本题共15分)6. 若集合力的元素个数为10,则其蓦集的元素个数为.7. 设a=af b, c), b=1, 2,作/： 4-b,则不同的函数个数为.8. 若力=12，r=<x.y>xa,ya,x+y=g,则r 的自反闭包为9. 结点数y与边数e满足 关系的无向连通图就是树.10. 设个体域d=a, b,c9则谓词公式(vxm(x)消去量词后的等值式为三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“尽管他接受了这个任务，但他没有完成好”翻译成命题公式.12. 将语句“今

4、天没有下雨翻译成命题公式.四、判断说明题(每小题7分，木题共14分)判断下列各题正误，并说明理由.13. 下面的推理是否正确，试予以说明.(1) (vx) f(x)-g (x)前提引入(2) f (y) -g (y)us (1).14. 若偏序集<4,的哈斯图如图二所示，则集合的最大元为s最小元不存在.g五. 计算题(每小题12分，本题共36分)15. 求(pv。)一(rv。)的合取范式.16. 设刀=0, 1, 2, 3, 4), 7?=(<x, y>xa, yea _h. x+y<0), s=<xf y>xea , yea x+y<3,试 求 r,

5、 s, r,s, r-i, s) r(r)17. 画一棵带权为1, 2, 2, 3, 4的最优二叉树，计算它们的权.六、证明题(本题共8分)18. 设g是一个阶无向简单图，是大于等于2的奇数.证明g与&中的奇数度顶点个数相等(° 是g的补图).试题解答一、单项选择题（每小题3分，本题共15分）1. a 2. b 3. b 4. d 5. c二、填空题（每小题3分，本题共15分）6. 10247. 88. （<1,1>,<2,2>9. e=v10. a （a） /a （b）（ u）三、逻辑公式翻译（每小题6分，本题共12分）11. 设他接受了这个任务，q

6、：他完成好了这个任务，（2分）pzq（6分）12. 设f：今天下雨，（2分）-yp.（6 分）四、判断说明题（每小题7分，本题共14分）13. 错误.（3分）（2）应为f （>） -g （x）,换名时，约束变元与自由变元不能混淆.（7分）14. 错误.（3分）集合a的最大元不存在，。是极大元.（7分）五、计算题（每小题12分，本题共36分）15. （pv2）一 （7?vg）（pv0） v （rv。）（4 分）<（-npa->e）v （rvq）顷v& v。）/ （2 v r v。）=（寸v&v。）ar 合取范式（12分）16. r=0,（2 分）5=<0,

7、0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>）（4 分）&s=0,（6 分）&'=0,（8 分）s】=s,（10 分）kr）=ia（12 分）权为 1x3+2x3+2x2+3x2+4x2=27（12 分）六、证明题（本题共8分）18.证明：因为"是奇数，所以阶完全图每个顶点度数为偶数，（3分）因此，若g中顶点y的度数为奇数，则在。中y的度数一定也是奇数，（6分）所以g与。中的奇数度

8、顶点个数相等.（8分）离散数学题库及答案二一、单项选择题（每小题3分，本题共15分）1.若集合4=1,（1, 2,则下列表述正确的是（）.a.b. 1或c.d. 2 ea2.已知一棵无向树中有8个顶点，4度、3度、2度的分支点各一个，的树叶数为（）.a.b. 4c. 3d- 53.设无向图g的邻接矩阵为0111110011100001100111010则g的边数为（)a. 1b. 7c. 6d. 144 .设集合a=a,则刀的蓦集为（)a. 。b。， ac.°，。d. (0, a5-下列公式中（）为永真式.a.c.二、填空题（每小题3分，本题共15分）6. 命题公式尸a tp的真值是

9、.7. 若无向树有5个结点，则的边数为8. 设正则也叉树的树叶数为分支数为j,则（"1）7 9. 设集合力=1, 2上的关系7? = （<1,1>,<1,2>,则在&中仅需加一个元素,就可使 新得到的关系为对称的.10. （vx）（a（x）b（xf z）vc（y）中的自由变元有,三、逻辑公式翻译（每小题6分，本题共12分）11. 将语句“今天上课.”翻译成命题公式.12. 将语句“他去操场锻炼，仅当他有时间.”翻译成命题公式.四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由.13. 设集合力=1, 2, b=3, 4）,从刀到8

10、的关系为（1,3）,贝是力到b的函数.14. 设g是一个有4个结点10条边的连通图，则g为平而图.五. 计算题（每小题12分，本题共36分）15. 试求出（pv。）一（rv。）的析取范式.16.设刀=1,1,2, 3=1, 2,试计算(2) c4ub)17. 图 g=<v9 £>,其中 v= %b,c,d, e=心)，(。,c),(% d), (b, c), (b, d),(c,力,对应边的权值依 次为1、2、3、1、4及5,试（1）画出g的图形;（2）写出g的邻接矩阵;（3）求出g权最小的生成树及其权值.六、证明题（本题共8分）18. 试证明：若r与s是集合刀上的自反关

11、系，贝u&ns也是集合力上的自反关系.试题解答一、单项选择题（每小题3分，本题共15分）1- b 2. d 3. b 4. c 5. b二、填空题（每小题3分，本题共15分）6.假（或f,或0）7.8.9.<2, 1>10.z, y三、逻辑公式翻译（每小题6分，本题共12分）11.设今天上课,（2分）（6分）则命题公式为：p.12.设f：他去操场锻炼，q：他有时间,（2分）则命题公式为：pt0（6分）四、判断说明题（每小题7分，本题共14分）13.错误.（3分）因为力中元素2没有3中元素与之对应，故/不是刀到3的函数.（7分）14.错误.（3分）不满足“设g是一个有v个结点

12、e条边的连通简单平面图，若则 ew3v6. ”(7分)五.计算题（每小题12分，本题共36分）15.(pv0) 一(&")-| (pv0v (rv。)(4分)16.(1)17.(2)(3)(2)(3)(1)（8分）<=>(npan 0v7?v0 (析取范式)c4u3) =1,2, 1,2a- c4c3) =(!, 1,2g的图形表示如图一所示:图一邻接矩阵:0111101111011110最小的生成树如图二中的粗线所示:（12 分）(4分)（8分）（12 分）（3分）（6分）30（10 分）b 1 c图二（12 分）权为：1+1+3=5六、证明题（本题共8分）18

13、.证明：设vxgj,因为&自反，所以x rx, bp<x,x>g7?；又因为s自反，所以xrx,即<x,x>es.即 vx, x>eros故acs自反.（4分）（6分）（8分）离散数学题库及答案三一、单项选择题（每小题3分，本题共15分）1.若集合a = a, ,则下列表述正确的是（）.a. /zo4c.d. 0ga2.命题公式（pvq）的合取范式是（）a.(pa2)b. (pa0) v (pvg)c.d. i (p /q)3.无向树r有8个结点,则t的边数为（）.a.be 7c. 8d.a.c.5.a.c.4.图g如图一所示,以下说法正确的是（）.a是割

14、点缶d是点割集图一下列公式成立的为（）.p/q = p/qqpnpb. 0 c是点割集d. c是点割集b. p->-iq = ttqd.pq)n。二、填空题（每小题3分，本题共15分）6. 设集合4=2.3,4, b=1,2, 3,4, r是刀到8的二元关系,7? = (<x.y > xe ay e<y则r的有序对集合为7. 如果r是非空集合力上的等价关系，aea,心,则可推知&中至少包含 等元素.8. 设g=<v,e>是有4个结点，8条边的无向连通图，则从g中删去 条边，可以确定图g的一棵生成树.9. 设g是具有个结点m条边个面的连通平面图，则m等

15、于10. 设个体域。=1,2,刀为大于1”，则谓词公式(3x)ax)的真值为三、逻辑公式翻译(每小题6分，木题共12分)11. 将语句“今天考试，明天放假”翻译成命题公式.12. 将语句“我去旅游，仅当我有时间”翻译成命题公式.四、判断说明题(每小题7分，本题共14分)判断下列各题正误，并说明理由.13. 如果图g是无向图，且其结点度数均为偶数，则图g是欧拉图.14. 若偏序集v4,人>的哈斯图如图二所示，则集合z的最大元为最小元是人五. 计算题(每小题12分，本题共36分)15 .设谓词公式(女)(刀(x, y) t (vz)5(y, x, z),试(1) 写出量词的辖域；(2)指出该

16、公式的自由变元和约束变元.16. 设集合 /=,1,2, 8=1,1,2,试计算(1) c48) ；(2) c4c1b) ；(3) axb.17. 设 g=<v, e>, v=v, v2> 巧，v4 ), e=(vi,v3), (v2,v3), (v2,v4)，(巧皿)，试(1) 给出g的图形表示； (2)写出其邻接矩阵；(3) 求出每个结点的度数；(4)画出其补图的图形.六、证明题(本题共8分)18. 设力，b是任意集合，试证明：若ax4=bxb,则试题解答（供参考）一、单项选择题（每小题3分，本题共15分）1. a 2. c 3. b 4. b 5. d二、填空题（每小题

17、3分，本题共15分）6. （<2, 2>, <2, 3>, <2,4>, <3, 3>）, <3, 4>, <4, 4>）7. <a, a >, < h, b>8. 59 . n+k-210. 真（或t,或1）三、逻辑公式翻译（每小题4分，本题共12分）11. 设p：今天考试，q：明天放假.（2分）则命题公式为：pa0（6分）12. 设f：我去旅游，q：我有时间，（2分）则命题公式为：pt0（6分）四、判断说明题（每小题7分，木题共14分）13. 错误.（3分）当图g不连通时图g不为欧拉图.（7分）

18、14. 错误.（3分）集合力的最大元与最小元不存在，a是极大元，/是极小元，（7分）五. 计算题（每小题12分，本题共36分）15. （1）女量词的辖域为以（x,v）t（vz）33,x,z）,（3 分）vz量词的辖域为x, z）,（6分）（2）自由变元为以（x,v）t（vz）33,x,z）中的，（9分）约束变元为x与z（12分）16. （1） z3=1,2（4 分）（2）acib=1（8 分）(3) 4x8=v1,1>, v1,1,2>, vl,l>, vl, 1,2>, <2,1>, v2, 1,2> (12 分)17. (1) g的图形表示为(如图

19、三)：v3（2）邻接矩阵:0 0 100 0 11110 10 110(3) v, v2, v3, v4结点的度数依次为b 2, 3, 2（9分）（4）补图如图四所示:图四六、证明题（本题共8分）18. 证明：设 xea9 则v«x, x>eaxa,（1分）因为 axa=bxb,故x>wbxb,则有（3分）所以aqb.（5分）（6分）因为axa=bxb,故v，x>eaxa,则有xea,所以（7分）故得a=b.（8分）离散数学题库及答案四一、单项选择题（每小题3分，本题共15分）1. 设 a=(1，3.5,7,9).r=(2，6),a 到 h 的关系 r-，：vz .

20、>! r-y-1) .则 r=(>.a. (<u2>,<2.3>.<3.4>>h(vl.2>,v3.4>v5.6>g <1.1>,<2,2>.<3.6>).(v3.2>v54>,v?6>)2. 若餐合a =.则下列表芯正确的是().a. (ciemcowac. (u,b6ad.0ea3. 段个体it为集合(1.2.34.5 .则公式(v)3少(工+=5)的解释可为().a.存在一整数g有整数y滴足x+>=5a对任一整数工存在整数y滴足*+=5c. 存在一整数4对任

21、恿整数y满足工+=5d. 任一整数工对任意整致y清足x+y=54. 没仁为连通无向图.蜗(时,a中存在欧拉回用.a.g存在两个tsfttjm数的结点b.g存在一个奇数度数的常点gg不存在奇数度数的结点d.g存。偶数度数的结点乩n阶无向完全图k.的边数及每个结点的度敬分别是().a. jt(n 1)与 n11 ji(w-*1)/2 与 ”一1c w 1 与 nd. n(n 1)与 « i二、填空题(每小题3分，本题共15分)6. 设堡 & 1一1.2.3) =,：2.3).(/=口.4,删.41)(3一()=7. 设af 08f.2l" h 从到b的画数/ =7v1&

22、gt;vo.2>.从b 到c的函数拜=(<1.6><2心>).荆旷/等于.8. 设g = vve>职一个图.|e| = m.则“的捎点度敝之和为9. 设g是代有茶边&个而的连通平面图.则刀+*-2=1d，设中怵城本=1.？.3.1j)为的2倍大于站.刖周刊公式iv那.4(/)的底值为三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“如果他掌握了计算机的用法，那么他就能完成这项工作”翻译成命题公式.12. 将语句“前天下雨，昨天还是下雨”翻译成命题公式.四、判断说明题(判断各题正误，并说明理由.每小题7分，本题共14分)13. 段.1 = %

23、 , a. c ) r ( v , > < a . /，a v r v 以，6 > v 内, > , v 右，4 a vrm> 姻r是等价关系.14. ( vx)cp< r)aqy)f rtr>)中世词 丫 的辖帔为(p。)aq( y)l五、计算题(每小题12分，本题共36分)15. 设陞台八=la,/，” .d)hr站日)，试”算(1)4 ubi(2)a/h(3)axb.'st v， e > , v* = < h t»，,口,. £ = （叫."c ）（玖,饥）.（叫.口、）.化. 5 > ,（

24、» 2.）.试（l>纷出g的图形&示，12>耳出其邻也如所，3）求出每个靖点的度，>踊出北补图的图形.i 7.试利用kruskn w伏未出如卜所况m技图中的/»小生成俐（要求写出求解3项，.井 未此条小生成列的枳.试题答案一单项选探bh每小题3分,本18共恃分）1.02.a3.b4.c5.h二. 填空!（每小超3分.本弛共15分）6. （1.2.3）7. （<<i.6>.<d.a>）«. 2。（或：2|e|）9m10. 假（或f.或。）三. 谣辐公式翩泽（每小聘6分.本息共12分）il i» pjl

25、fctw了计算机的用法,q：他推完成这项工作-（2分）删命题公式为，pfq（6分）12. 设p,前天下雨.q冲天还是下阑.（2分）则命88公式为：paq.；（6分）四、判断说明网（督小18 7分,本18共m分）13. 部误.（3分）r不是等价关系.因r中包含<a.b><ba>，但不包含v<2/>故不满足传递性：（1 分）14. 销误“心分）暗域为紧惟st词v之后的梭小子公式（p（x）aqc.y）-r（x）.7分）五计算1!（每小12分,本11共36分）15. n）aub =（a0cd）i（4 分（2a 8 = （c </） i(3) 4 xb(<

26、a .a>.<a.b>.<b.u>,<b.b>.<c.u>.<c 5> vd g > vd e>)j6.（i）g的图形&示ftn图一所示,(2郊接矩阵， 0 1 1 1 10 10 110 1 10 10图一（3分）6分）(3)血只(口)= 3.drg(i>j) - 2>drg(vj)&3tdege ) = 2(4补图如图二所示,（9分）o（12 分）（6分）图二17.用kruskal算往求产生的最小生&树.步界为:1 .选小=1/1?uh戏t/）=3选小=w( v> v?

27、4 选 ft =山巧 wm.m)r9 ,选 = wms>=l8 .遗 w33=22.ii e.=y囹三（9分）ia小生应用的权 m=i十3 + 1 + 94 ir+22=57< 12分）六. 证明题（本js共&分h18, m wt(!) p vqp（1分）ppou fill前提以分qtcd(2)rm分)aqtf2)(3)/（5分）-(-p v 9r(nech分)(6)f 1 p-* 二 q >t(5)e（7分）<7)p一q)cp埸则<8分)iftluhlhiie删过慢中.公式引用的次序诃以不同般引用的提正琦特1分.利川俩个公k 团出有效结伯格1成2分,眼后

28、同出站论得2或1分另.可以用页值表脸证.离散数学题库及答案五单项选择题（每小题3分，本题共15分）1. 设 a = 1.2,3,1),8= (2,3,4,a 到 b 的关系 r - <x .>> i z 6 a g b .且.r + y= 5.tt!r = ().a. <<2>.v13>,v23>)el <1.4>.<2.3>.<3»2>>(：.(v1.1>,v2.2>,v3,2>)d. (<3.2>,<2,4>.<3,4>>2. 若集

29、合a = m6,r.d).则下列表述正的的是<.a.06ac«m.d£ad. u.6jga3 .设个体域为整数韭.燃公式(vx)(3y)(x->=2>的解释可为().a. 存在一整数工有整数y满足x-y-2b. 存在一建数工对任意整数y满足工一y = 2c. 对任一整数工存在整数滴足x-y-2d. 任一整数1对任意整数满足x-> = 24. "阶无向完全图k,的边数及每个结点的度数分别是().a. n(w 与b. n( w 1)与 一1cn 】与”d. w(n 1)/2 与 rr 15. 设g为连通无向图.则( 时弓中存在欧拉回路.a.g不

30、存在奇数度数的结点b.g存在一个新数度数的结点c.g存在两个奇数度数的结点d.g存在偶数度数的结点甫分评卷人二、填空题（每小18 3分,本a共15分）6. 设集含工是小于4的正整数） 用集合的列举法.7. 设 a = （l,2）,t2）,ctl,2.从 a 到 b 的函数/ = （vlu>,v2,q>.从 b到c的函致g = （<a2>,v6.l>.则复合函数.8. 设g-<v.e>是一个图，结或度敬之和为30.则g的边数为9. 设g是具有，个结点桁条边个面的连通平面图，姻”+a-2=.10. 设个体域d = （2,3.4>.a（i）为七小于3”

31、，则谓同公式（vjhag ）的真值为得分评卷人三!！福公式小is 6分，本原共12分）11. 将语句“如果今天下雨.那么明天的比赛就要延期.”疆译成命题公式.得分评卷人12. 将语句“地球是圆的，太阳也是圆的.”翻译成命题公式.四、判断说明ih（判断各题正误，井说明理由每小h 7分，本题共14分）13. 设 aa.b.c.d .r<a.h>9<b,a>,<a.a>9<b.b>.<c>,则 r 是等 价关系.14. ( vx)(p(x)aq(y)-r(x)中量词 v 的辖域为(p(x> aq(>).得分评卷入五计算魁（每小h

32、 12分.本慧共36分）15. 设集合a =试计算(l)a(jhi(2)4-3,(3)axb.16. 设 g = <vte>t v « (v| t vt ) e = (v| ) < (vj t (vi. v<) > (1/1 ti»i )(l>给出g的图形衰示8(2)写出其邻接矩阵i(3)戒出每个站点的度数,(4)®出其补图的图形.17. 试利用kru9kd算法求出如下所示赋权图中的1ft小生或树(妻求写出求薪步辕，并 求此最小生成树的权.得分评卷人六、证明18(本题共8分)18.成征明r （p-q）.试题及答案-项iswhim

33、小m3分,本ai共is分）i. b2.d3.c4. d&a二, 堵空jb（每小1«3分.本1«共15分）6. （i.2.3）7. <<1.2>.<2.1»9. m10. fl<af.«0>三、il辑公式小h6分.本hi共12分）h.今天下ifl.qzi天的比赛就要14期.（2分）副命ms公式为6分）12.仗卜地球屈圆的，。太阳是圆的.2分）wlifrm公式为lpq.（6 分四、判断说明18（每小jw 7分,本jb共14分）ix wim.（3 分）r不是等价关系.因r中不含vm>.故不fmmfl反性.（7分

34、）m.正确.“分）之后的 jft 小子公 x（p（jc）aq（y>）.（7 分）五小h技分.本h共36分）15. au8m.y</i（4 分）（2m-b-（ah（8 分）（3）a xb <u.6 >.<a .（>,<« i>9<b.b>.<b.c>.<b.d>t<r.b>.<c.（12 分）16. (1 )g的图形表如图一所不:(2邻接矩阵,viww4图一(3分)d i i r10 10110 110 10 _(6分(3)<ieg(vi)= 3.dc&3$= 2,deg

35、(0)= 3deg(s> = 2(4补09如图二所示i9分)图二w(v| .vr) = l选 e(w(vr ) = 1选 cl v?1f4w(vj fvs) = 2选 = v|v<w(v>=3选 =17.用kruskal w法求产生的感小生成树.步骤为,w(vt vf ) = 4 选 cs =vjv? w (vj f vt > = 5 ij ci 33 v$v? 最小生成钙如图三所示.6分）图三（9分）最小生成树的权w(t) = 1 + 1 + 2 + 3 + 4 + 5=16.（12 分）说明，用其他方法.结果正确参照给分.六证明18（本境共8分）18.证明：(l)p

36、-q（1分）(3)q(4)paq(5up v 9(6uq)p（附加前提）t(2)(3)/t(4)et(5>e（2分）（4分）5分）（6分（7分）(7pr(rq（8分）说明：因be明过程中,公式引用的次序可以不同一般引用前提正确得1分,利用两个公式 得出有效结论得1或2分，景后得出结论得2或1分.另可以用真值表验证.离散数学题库及答案六一、单项选择题（每小题3分，本题共15分）若集台人=(1.2.3.u .则下列我还不正确的m(a2.3)£ab. a 1.2,3.1)c, (1.23,4)w人d. lea2. 若无向图。的结点度数之和为20,则r；的边数为( >a. 10a

37、 20c.30d.5x无向图g是根树，结成数为1)的(；的边数为(>.a.sr. 10q9dji4. ft a()：j是人”(了)口是学生,删母瓯“村的人是学生”可荷门化为(a. r ( v«t)(惑_r)f)b. ( 3)(a(x) ab(x)c (yx)(a(x) ab(x)i), r <a r hj > 】5. 下面的推理正唏的是().a* < 1h v x)f(x)-7(x)前提引人<2)f(>)-*g(y)us (1>.&1)( 3 -r)f( j )-*g (x )前提引入(2)f(y)g(y)us().c. (1)( 3

38、)(f( f >-*g(±>)的提引人fjm。()es(1).d. (1)( 3jxf(x)-*glr)前捉引人(2)f(ylt；y)es(d.二、填空题(每小题3分，本题共15分)6. 设a = “.2.bu 1.2.3 则a到b上不同的函散个散为7. fin个靖点的无向完全图的边数为%若无向图g中存在欧枚路但不存在欧拉回路，则6的布散度敬的结点有 9. 设(；是a 10个结点的无向连通图.结点的度教之和为30,则从g中jh去条边后使之变成树-10, 设个体域d = < 1.2.3.1).则明词公式(如 >人m )酒去旬俱后的等值式为 三、逻辑公式翻译(每小题6分，本题共12分)11. 将语句“昨天下雨"翻译成命题公式.12. 将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式.四、判断说明题(判断各题正误，并说明理由.每小题7分，木题共14分)ix存在果合a与使得与同时成立.14, 完全图k,是平面图.五、计算题(每小题12分，本题共36分)15. 坟偏序集va,r的哈斯图如f.b为a的升集共中日=f仇”.城；!与出r的关备艘达式;(2,凯出关系r的关系图，(3求出h的最大元,极大元.上界.16. 设图 g <vte>.v