电大历年离散数学试题汇总

1、计算机科学与技术专业 级第二学期离散数学试题2012年1月一、单项选择题（每小题3分，本题共15分）1C 2C 3B 4A 5D 1若集合A的元素个数为10，则其幂集的元素个数为（ ） A10 B100 C1024 D12设A=a, b，B=1, 2，R1，R2，R3是A到B的二元关系，且R1=<a，2>, <a，1>，R2=<a，1>, <a，2>, <b，1>，R3=<a，1>, <b，2>，则（ ）是从A到B的函数 AR1和R2 BR2 CR3 DR1和R33设A=1, 2, 3, 4, 5, 6, 7,

2、 8，R是A上的整除关系，B=2, 4, 6，则集合B的最大元、最小元、上界、下界依次为 ( ) A8、2、8、2 B无、2、无、2 C6、2、6、2 D8、1、6、14若完全图G中有n个结点(n2)，m条边，则当（ ）时，图G中存在欧拉回路An为奇数 Bn为偶数 Cm为奇数 Dm为偶数5已知图G的邻接矩阵为 则G有（ ） A6点，8边 B6点，6边 C5点，8边 D5点，6边二、填空题（每小题3分，本题共15分）6设集合Aa，那么集合A的幂集是 Æ,a 7若R1和R2是A上的对称关系，则R1R2，R1R2，R1-R2 ，R2-R1中对称关系有 4 个 8设图G是有5个结点的连通图，

3、结点度数总和为10，则可从G中删去 1 条边后使之变成树9设连通平面图G的结点数为5，边数为6，则面数为 3 10设个体域Da, b，则谓词公式("x)(A(x)B（x）消去量词后的等值式为 (A (a)B (b)(A（a）B（b） 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“今天有联欢活动，明天有文艺晚会”翻译成命题公式设P：今天有联欢活动，Q：明天有文艺晚会， （2分） PQ （6分）12将语句“如果小王来，则小李去” 翻译成命题公式设 P：小王来，Q：小李去 （2分）P Q （6分）四、判断说明题（每小题7分，本题共14分）ooooabcd图一判断下列各题正误，并说

4、明理由13若偏序集<A，R>的哈斯图如图一所示， 则集合A的最大元为a，极小元不存在错误 （3分）对于集合A的任意元素x，均有<x, a>ÎR（或xRa），所以a是集合A中的最大元（5分）但按照极小元的定义，在集合A中b,c,d均是极小元 （7分）14P（PQ）P为永假式错误 （3分）P（PQ）P是由P（PQ）与P组成的析取式，如果P的值为真，则P（PQ）P为真， （5分）如果P的值为假，则P与PQ为真，即P（PQ）为真，也即P（PQ）P为真，所以P（PQ）P是永真式 （7分）另种说明：P（PQ）P是由P（PQ）与P组成的析取式，只要其中一项为真，则整个公式为

5、真 （5分）可以看到，不论P的值为真或为假，P（PQ）与P总有一个为真， 所以P（PQ）P是永真式 （7分）或用等价演算P（PQ）PÛT五计算题（每小题12分，本题共36分）15设集合A=1，2，3，4，R=<x, y>|x, yÎA；|x-y|=1或x-y=0，试（1）写出R的有序对表示； （2）画出R的关系图；（3）说明R满足自反性，不满足传递性15（1）R=<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3

6、,4>,<4,3> （3分）（2）关系图如图二： 图二 （6分）（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的 （9分）因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的 （12分）16设图G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1, v2)，(v1, v3)，(v2, v4)，(v3, v5)，(v4, v5) ，试(1) 画出G的图形表示；(2) 写出其邻

7、接矩阵；oooov1v2v3v4图三v5o(3) 求出每个结点的度数；(4) 画出图G的补图的图形16（1）关系图如图三： （3分）（2）邻接矩阵 （6分）（3）deg(v1)=2deg(v2)=2deg(v3)=2deg(v4)=2oooov1v2v3v4图四v5odeg(v5)=2 （9分） （4）补图如图四 （12分）17求P®QR的合取范式与主析取范式P（RQ）ÛP(RQ) （4分）Û （PQ）（PR） （合取范式） （6分） P（RQ）ÛP(RQ)Û(P(QQ) )(RQ) （7分）Û(PQ)(PQ)(RQ) （8分）

8、19;(PQ) (RR)(PQ )(RQ ) （9分）Û(PQR)(PQR)(PQ)(RQ) （10分）Û(PQR)(PQR)(PQ)(RR)(RQ)Û(PQR)(PQR)(PQR)(PQR)(RQ)Û(PQR)(PQR)(PQR) (PQR)(PP)(RQ)Û(PQR)(PQR)(PQR)(PQR) (PRQ) （主析取范式） （12分）说明：此题解法步骤多样，若能按正确步骤求得结果，均可给分六、证明题（本题共8分）18设连通无向图G有14条边，3个4度顶点，4个3度顶点，其它顶点的度数均小于3，试说明G中可能有的顶点数证明： 可利用数列可图

9、化及握手定理解答顶点度数和为2´14=28， （2分）28-（3´4+4´3）=4，则知其他顶点度数和为4， （4分）对于有限图，若无零度顶点，则除4度及3度顶点外，可能的顶点情况有：2个2度点；1个2度点和2个1度点；4个1度点， （6分）即对应图的顶点数分别至少为9、10、11 （8分）2011年 7月一、单项选择题（每小题3分，本题共15分）1A 2C 3C 4D 5B1若集合A=1，1，2，1，2，则下列表述正确的是( ) A2ÎA B1，2ÌAC1ÏA D2 Ì A2设G为无向图，则下列结论成立的是 ( ) A无向

10、图G的结点的度数等于边数的两倍 B无向图G的结点的度数等于边数 C无向图G的结点的度数之和等于边数的两倍 D无向图G的结点的度数之和等于边数ooooooabcdef3图G如图一所示，以下说法正确的是( ) A(a，b)是边割集 B a，c是点割集 Cd是点割集 D (c，d)是边割集 图一4设集合A=1，则A的幂集为( )A1 B1，1CÆ，1 DÆ，15设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)二、填空题（每小

11、题3分，本题共15分）6命题公式的真值是 真（或T，或1） 7若无向图T是连通的，则T的结点数v与边数e满足关系v= e+1 时，T是树8无向图G是欧拉图的充分必要条件是 G是连通的且结点度数都是偶数 9设集合A=1，2上的关系R<2,2>,<1,2>，则在R中仅需加入一个元素 <1, 1> ，就可使新得到的关系为自反的10("x)(P(x)R(y)S(z) 中的约束变元有 x 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“雪是黑色的”翻译成命题公式设P：雪是黑色的， （2分）则命题公式为：P （6分）12将语句“如果明天下雨，则我们就在

12、室内上体育课”翻译成命题公式设 P：如果明天下雨， Q：我们在室内上体育课， （2分）则命题公式为：P ®Q （6分） 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13设集合A=1，2，B=3，4，从A到B的关系为f=<1, 3>，<1, 4>，则f是A到B的函数错误 （3分）因为A中元素1有B中两个不同的元素与之对应，故f不是A到B的函数 （7分）14设G是一个连通平面图，有5个结点9条边，则G有6个面正确 （3分）因G是一个连通平面图，满足欧拉定理，有v-e+r=2，所以r=2-（v-e）=2-（5-9）=6 （7分） 五计算题（

13、每小题12分，本题共36分）15试求出P（RQ）的合取范式P（RQ）ÛP（RQ） （6分） Û (PR) （PQ）（合取范式） （12分）16设A=1, 1, 2，1，B= 1, 2, 2，试计算（1）（AB） （2）（AB） （3）（AB）-A（1）（AB）=1 （4分） （2）（AB）=1, 2, 1, 2, 1, 2 （8分） （3）（AB）-A =Æ （12分）17试画一棵带权为2, 3, 3, 4, 5,的最优二叉树,并计算该最优二叉树的权最优二叉树如图二所示 ooooooooo23345510717 （10分） 图二 权为2´3+3´

14、;3+3´2+4´2+5´2=39 （12分）六、证明题（本题共8分）18试证明：若R与S是集合A上的对称关系，则RS也是集合A上的对称关系证明：设"x，yÎA，因为R对称，所以若<x, y>ÎR，则<y, x>ÎR （2分） 因为S对称，所以若<x, y>ÎS，则<y, x>ÎS （4分） 于是若<x, y>ÎRS 则<x, y>ÎR且<x, y>ÎS 即 <y, x>Î

15、;R且<y, x>ÎS （6分） 也即<y, x>Î RS，故RS是对称的 （8分）中央广播电视大学20102011学年度第一学期“开放本科”期末考试离散数学（本）试题2011年1月一、单项选择题（每小题3分，本题共15分）1A 2D 3B 4D 5C1若集合A a，1，则下列表述正确的是( ) A1ÎA B1ÍACaÎA DÆÎA 2设图G<V, E>，vÎV，则下列结论成立的是 ( ) Adeg(v)=2½E½ Bdeg(v)=½E½

16、C D3如图一所示，以下说法正确的是 ( )A(e, c)是割边 B(d, e)是割边ooooabcd图一oeC(b, a)是割边 D(b, c)是割边 4命题公式（PQ）的合取范式是 ( ) AP B（PQ） C（PP） D（PQ） 5下列等价公式成立的为( )APÙQÛPÚQ BØQ®PÛP®Q CØPÙP ÛØQÙQ DØPÚP ÛQ二、填空题（每小题3分，本题共15分）6设集合A=0, 1, 2，B=1,2, 3, 4,，R是A到B的二元

17、关系，则R的有序对集合为 <1, 1>，<1, 2>，<2, 1>，<2, 2> 7设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式 v-e+r=2 8设G<V, E>是有20个结点，25条边的连通图，则从G中删去 6 条边，可以确定图G的一棵生成树9无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且 连通 10设个体域D1,2，则谓词公式消去量词后的等值式为 A(1) ÙA(2) 三、逻辑公式翻译（每小题6分，本题共12分） 11将语句“如果小李学习努力，那么他就会取得好成绩”

18、翻译成命题公式12将语句“小张学习努力，小王取得好成绩”翻译成命题公式11设P：小李学习努力，Q：小李会取得好成绩， （2分）P®Q （6分）12设P：小张学习努力，Q：小王取得好成绩， （2分）PÙQ （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13如果R1和R2是A上的自反关系，则R1ÇR2是自反的14如图二所示的图中存在一条欧拉回路oooo图二o 13正确 （3分）R1和R2是自反的，"x ÎA，<x, x> Î R1，<x, x> ÎR2， 则<x, x

19、> Î R1ÇR2， 所以R1ÇR2是自反的 （7分）14正确 （3分）因为图G为连通的，且其中每个顶点的度数为偶数 （7分）五计算题（每小题12分，本题共36分）15设A=2,1,2，B=1,1,2，试计算（1）（A-B）； （2）（AB）； （3）A×B16设G=<V，E>，V= v1，v2，v3，v4，v5，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，试（1）给出G的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形17设谓词公式，试（1）写出量词的辖域；

20、 （2）指出该公式的自由变元和约束变元15（1）A-B =2,2 （4分）（2）AB =1 （8分）（3）A×B=<2,1>，<2,1,2>，<1,1>，<1, 1,2>，<2,1>，<2, 1,2> （12分）oooov1v2v3v4图三v5o16（1）G的图形表示如图三： （3分）（2）邻接矩阵： （6分）（3）v1，v2，v3，v4，v5结点的度数依次为1，2，4，2，1 （9分）oooov1v2v3v4图四v5o（4）补图如图四： （12分）17（1）$x量词的辖域为， （2分）"z量词的辖域为

21、, （4分） "y量词的辖域为 （6分）（2）自由变元为中的y，以及中的z （9分）约束变元为中的x与中的z，以及中的y （12分）六、证明题（本题共8分）18试证明集合等式AÈ (BÇC)=(AÈB) Ç (AÈC) 18证明：设S= AÈ (BÇC)，T=(AÈB) Ç (AÈC)，若xS，则xA或xBÇC，（1分）即 xA或xB 且 xA或xC （2分）也即xAÈB 且 xAÈC ， （3分）即 xT，所以SÍT （4分）反之，若xT，则x

22、AÈB 且 xAÈC， （5分） 即xA或xB 且 xA或xC， （6分） 也即xA或xBÇC，即xS，所以TÍS （7分） 因此T=S （8分）2011年1月一、单项选择题（每小题3分，本题共15分）1D 2B 3C 4A 5B1若集合A=a，b，B= a， a，b ，则（ ） AAÏB BAÍB CAÌB DAÎB2集合A=x|x为小于10的自然数，集合A上的关系R=<x，y>|x+y=10且x, y A，则R的性质为（ ） A自反的 B对称的 C传递且对称的 D反自反且传递的3设有向图（a）、（b

23、）、（c）与（d）如图一所示，则下列结论成立的是 ( ) 图一 A（a）仅为弱连通的 B（b）仅为弱连通的C（c）仅为弱连通的 D（d）仅为弱连通的4设图G的邻接矩阵为则G的边数为( )A5 B6 C7 D85下列公式 ( )为永真式AØPÙØQ«PÚQ B(P®(ØQ®P)«(ØP®(P®Q) C(Q®(PÚQ) «(ØQÙ(PÚQ) D(ØPÚ(PÙQ) «Q二、填空题（每

24、小题3分，本题共15分）6设集合A1，2，3，那么集合A的幂集是 Æ,1,2 ,3 ,1,2,1,3,2,3,1,2,3 7设A=a，b，B=1，2，作f：AB，则不同的函数个数为 4 8若A=1,2，R=<x, y>|xÎA, yÎA, x+y<4，则R的自反闭包为 <1,1>,<2,2>,<1,2>,<2,1> 9无向连通图在结点数v与边数e满足 e=v-1 关系时是树10("x)(A(x)B(x)C(x，y)中的自由变元为 C(x，y )中的x与y 三、逻辑公式翻译（每小题6分，本题

25、共12分） 11将语句“他们去旅游，仅当明天天晴”翻译成命题公式12将语句“今天没有下雪”翻译成命题公式11设P：他们去旅游，Q：明天天晴， （2分） PQ （6分）12设P：今天下雪， （2分）Ø P （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13汉密尔顿图一定是欧拉图oooo图二错误 （3分）存在汉密尔顿图不是欧拉图 （5分）反例见图二 （7分）14下面的推理是否正确，试予以说明 (1) （$x）（F（x）G（y） 前提引入 (2) F（y）G（y） ES（1）1、错误 （3分）（2）应为F（a）G（y），换名时，约束变元与自由变元不能混淆 （

26、7分）五计算题（每小题12分，本题共36分） 15设A=0，1，2，3，4，5，6，R=<x，y>|xÎA，yÎA且x+y<1，S=<x，y>|xÎA，yÎA且x+y£3，试求R，S，R·S，R-1，S-1，r(R)R=<0,0> （2分）S=<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0> （4分） R&

27、#183;S=<0,0>,<0,1>,<0,2>,<0,3> （6分）R-1=<0,0> （8分）S-1= S （10分）r(R)=IA （12分）16画一棵带权为1, 2, 2, 3, 6的最优二叉树,计算它们的权14 最优二叉树如图四：86oo5o3ooo3221oo 图四 （10分）权为：1´3+2´3+2´3+3´3+6´1=30 （12分）注: 其他正确的最优二叉树参照给分17求（PQ）（RQ）的析取范式，合取范式（PQ）（RQ） ÛØ（PQ）（RQ） （

28、4分） Û(ØPØQ)（RQ） Û(ØPRQ)(ØQRQ)Û(ØPRQ) 析取、合取范式 （12分） 注: 其他正确答案参照给分六、证明题（本题共8分）18试证明集合等式AÇ (BÈC)=(AÇB) È (AÇC)证明：设S=A(BC)，T=(AB)(AC)， 若xS，则xA且xBC，即 xA且xB 或 xA且xC， 也即xAB 或 xAC ，即 xT，所以SÍT （4分） 反之，若xT，则xAB 或 xAC， 即xA且xB 或 xA且xC 也即xA且xB

29、C，即xS，所以TÍS 因此T=S （8分）2010年 7月一、单项选择题（每小题3分，本题共15分）1B 2D 3B 4C 5B1若集合A=1，2，1，2，则下列表述正确的是( ) A2ÌA B1ÌAC1ÏA D2 Î A2已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )A6 B4 C3 D53设无向图G的邻接矩阵为,则G的边数为( )A1 B7 C6 D144设集合A=a，则A的幂集为( )Aa Ba，aCÆ，a DÆ，a5下列公式中 ( )为永真式AØAÙØ

30、B « ØAÚØB BØAÙØB « Ø(AÚB) CØAÙØB « AÚB DØAÙØB « Ø(AÙB)二、填空题（每小题3分，本题共15分）6命题公式的真值是 假（或F，或0） 7若无向树T有5个结点，则T的边数为 4 8设正则m叉树的树叶数为t，分支数为i，则(m-1)i= t-1 9设集合A=1，2上的关系R<1, 1>,<1, 2>，则在R中仅需加一个

31、元素 <2, 1> ，就可使新得到的关系为对称的10("x)(A(x)B(x，z)C(y)中的自由变元有 z，y 三、逻辑公式翻译（每小题6分，本题共12分）11将语句“今天上课”翻译成命题公式设P：今天上课， （2分） 则命题公式为：P （6分）12将语句“他去操场锻炼，仅当他有时间”翻译成命题公式设 P：他去操场锻炼，Q：他有时间， （2分） 则命题公式为：P ®Q （6分） 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13设集合A=1，2，B=3，4，从A到B的关系为f=<1, 3>，则f是A到B的函数14设G是一个有

32、4个结点10条边的连通图，则G为平面图13错误 （3分）因为A中元素2没有B中元素与之对应，故f不是A到B的函数 （7分）14错误 （3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若v3，则e3v-6” （7分） 五计算题（每小题12分，本题共36分）15试求出（PQ）（RQ）的析取范式（PQ）（RQ）Û (PQ)（RQ） （4分） Û (PQ)（RQ） （8分） Û (PQ)RQ（析取范式） （12分）16设A=1, 1, 2，B= 1, 2，试计算（1）AB （2）AB （3）A -（AB）（1）AB=1 （4分）（2）AB=1, 2, 1, 2

33、（8分）（3） A-（AB）=1, 2 （12分）17图G=<V, E>，其中V= a, b, c, d ，E= (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形； （2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值图一ooooabcd112453（1）G的图形表示如图一所示： （3分）（2）邻接矩阵：图二ooooabcd112453 （6分）（3）最小的生成树如图二中的粗线所示： （10分）权为：1+1+3=5 （12分）六、证明题（本题共8分）18试证明：若R与

34、S是集合A上的自反关系，则RS也是集合A上的自反关系证明：设"xÎA，因为R自反，所以x R x，即< x, x>ÎR； 又因为S自反，所以x R x，即< x, x >ÎS （4分） 即< x, x>ÎRS （6分） 故RS自反 （8分）2010年1月一、单项选择题（每小题3分，本题共15分）1A 2C 3B 4B 5D1若集合A a，a，则下列表述正确的是( ) AaÍA BaÍACa，aÎA DÆÎA2命题公式（PQ）的合取范式是 ( ) A（PQ） B

35、（PQ）（PQ） C（PQ） DØ（ØPØQ）3无向树T有8个结点，则T的边数为( )A6 B7 C8 D9 4图G如图一所示，以下说法正确的是 ( )Aa是割点 Bb, c是点割集Cb, d是点割集 Dc是点割集 图一5下列公式成立的为( )AØPØQ Û PQ BP®ØQ Û ØP®Q CQ®P Þ P DØP(PQ)ÞQ二、填空题（每小题3分，本题共15分）6设集合A=2, 3, 4，B=1, 2, 3, 4，R是A到B的二元关系，则R的有序对集合为 <2, 2>，<2, 3>，<2, 4>，<3, 3>，<3, 4>，<4, 4>