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

计算机科学与技术专业 级第二学期离散数学试题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=, ，r2=, , ，r3=, ，则（ ）是从a到b的函数 ar1和r2 br2 cr3 dr1和r33设a=1, 2, 3, 4, 5, 6, 7, 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个结点的连通图，结点度数总和为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图一判断下列各题正误，并说明理由13若偏序集的哈斯图如图一所示， 则集合a的最大元为a，极小元不存在错误 （3分）对于集合a的任意元素x，均有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分）可以看到，不论p的值为真或为假，p（pq）与p总有一个为真， 所以p（pq）p是永真式 （7分）或用等价演算p（pq）pt五计算题（每小题12分，本题共36分）15设集合a=1，2，3，4，r=|x, ya；|x-y|=1或x-y=0，试（1）写出r的有序对表示； （2）画出r的关系图；（3）说明r满足自反性，不满足传递性15（1）r=, （3分）（2）关系图如图二： 图二 （6分）（3）因为,均属于r，即a的每个元素构成的有序对均在r中，故r在a上是自反的 （9分）因有与属于r，但不属于r，所以r在a上不是传递的 （12分）16设图g=，v= v1，v2，v3，v4，v5，e= (v1, v2)，(v1, v3)，(v2, v4)，(v3, v5)，(v4, v5) ，试(1) 画出g的图形表示；(2) 写出其邻接矩阵；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求pqr的合取范式与主析取范式p（rq）p(rq) （4分） （pq）（pr） （合取范式） （6分） p（rq）p(rq)(p(qq) )(rq) （7分）(pq)(pq)(rq) （8分）(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中可能有的顶点数证明： 可利用数列可图化及握手定理解答顶点度数和为214=28， （2分）28-（34+43）=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，则下列表述正确的是( ) a2a b1，2ac1a d2 a2设g为无向图，则下列结论成立的是 ( ) a无向图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)二、填空题（每小题3分，本题共15分）6命题公式的真值是 真（或t，或1） 7若无向图t是连通的，则t的结点数v与边数e满足关系v= e+1 时，t是树8无向图g是欧拉图的充分必要条件是 g是连通的且结点度数都是偶数 9设集合a=1，2上的关系r,，则在r中仅需加入一个元素 ，就可使新得到的关系为自反的10(x)(p(x)r(y)s(z) 中的约束变元有 x 三、逻辑公式翻译（每小题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=，则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分） 五计算题（每小题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分） 图二 权为23+33+32+42+52=39 （12分）六、证明题（本题共8分）18试证明：若r与s是集合a上的对称关系，则rs也是集合a上的对称关系证明：设x，ya，因为r对称，所以若r，则r （2分） 因为s对称，所以若s，则s （4分） 于是若rs 则r且s 即 r且s （6分） 也即 rs，故rs是对称的 （8分）中央广播电视大学20102011学年度第一学期“开放本科”期末考试离散数学（本）试题2011年1月一、单项选择题（每小题3分，本题共15分）1a 2d 3b 4d 5c1若集合a a，1，则下列表述正确的是( ) a1a b1acaa da 2设图g，vv，则下列结论成立的是 ( ) adeg(v)=2e bdeg(v)=e 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下列等价公式成立的为( )apqpq bqppq cpp qq dpp q二、填空题（每小题3分，本题共15分）6设集合a=0, 1, 2，b=1,2, 3, 4,，r是a到b的二元关系，则r的有序对集合为 ， 7设g是连通平面图，v, e, r分别表示g的结点数，边数和面数，则v，e和r满足的关系式 v-e+r=2 8设g是有20个结点，25条边的连通图，则从g中删去 6 条边，可以确定图g的一棵生成树9无向图g存在欧拉回路，当且仅当g所有结点的度数全为偶数且 连通 10设个体域d1,2，则谓词公式消去量词后的等值式为 a(1) a(2) 三、逻辑公式翻译（每小题6分，本题共12分） 11将语句“如果小李学习努力，那么他就会取得好成绩”翻译成命题公式12将语句“小张学习努力，小王取得好成绩”翻译成命题公式11设p：小李学习努力，q：小李会取得好成绩， （2分）pq （6分）12设p：小张学习努力，q：小王取得好成绩， （2分）pq （6分）四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由13如果r1和r2是a上的自反关系，则r1r2是自反的14如图二所示的图中存在一条欧拉回路oooo图二o 13正确 （3分）r1和r2是自反的，x a， r1， r2， 则 r1r2， 所以r1r2是自反的 （7分）14正确 （3分）因为图g为连通的，且其中每个顶点的度数为偶数 （7分）五计算题（每小题12分，本题共36分）15设a=2,1,2，b=1,1,2，试计算（1）（a-b）； （2）（ab）； （3）ab16设g=，v= v1，v2，v3，v4，v5，e= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，试（1）给出g的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形17设谓词公式，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元15（1）a-b =2,2 （4分）（2）ab =1 （8分）（3）ab=， （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量词的辖域为, （4分） y量词的辖域为 （6分）（2）自由变元为中的y，以及中的z （9分）约束变元为中的x与中的z，以及中的y （12分）六、证明题（本题共8分）18试证明集合等式a (bc)=(ab) (ac) 18证明：设s= a (bc)，t=(ab) (ac)，若xs，则xa或xbc，（1分）即 xa或xb 且 xa或xc （2分）也即xab 且 xac ， （3分）即 xt，所以st （4分）反之，若xt，则xab 且 xac， （5分） 即xa或xb 且 xa或xc， （6分） 也即xa或xbc，即xs，所以ts （7分） 因此t=s （8分）2011年1月一、单项选择题（每小题3分，本题共15分）1d 2b 3c 4a 5b1若集合a=a，b，b= a， a，b ，则（ ） aab bab cab dab2集合a=x|x为小于10的自然数，集合a上的关系r=|x+y=10且x, y a，则r的性质为（ ） a自反的 b对称的 c传递且对称的 d反自反且传递的3设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( ) 图一 a（a）仅为弱连通的 b（b）仅为弱连通的c（c）仅为弱连通的 d（d）仅为弱连通的4设图g的邻接矩阵为则g的边数为( )a5 b6 c7 d85下列公式 ( )为永真式apqpq b(p(qp)(p(pq) c(q(pq) (q(pq) d(p(pq) q二、填空题（每小题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=|xa, ya, x+y4，则r的自反闭包为 , 9无向连通图在结点数v与边数e满足 e=v-1 关系时是树10(x)(a(x)b(x)c(x，y)中的自由变元为 c(x，y )中的x与y 三、逻辑公式翻译（每小题6分，本题共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），换名时，约束变元与自由变元不能混淆 （7分）五计算题（每小题12分，本题共36分） 15设a=0，1，2，3，4，5，6，r=|xa，ya且x+y1，s=|xa，ya且x+y3，试求r，s，rs，r-1，s-1，r(r)r= （2分）s=, （4分） rs=, （6分）r-1= （8分）s-1= s （10分）r(r)=ia （12分）16画一棵带权为1, 2, 2, 3, 6的最优二叉树,计算它们的权14 最优二叉树如图四：86oo5o3ooo3221oo 图四 （10分）权为：13+23+23+33+61=30 （12分）注: 其他正确的最优二叉树参照给分17求（pq）（rq）的析取范式，合取范式（pq）（rq） （pq）（rq） （4分） (pq)（rq） (prq)(qrq)(prq) 析取、合取范式 （12分） 注: 其他正确答案参照给分六、证明题（本题共8分）18试证明集合等式a (bc)=(ab) (ac)证明：设s=a(bc)，t=(ab)(ac)， 若xs，则xa且xbc，即 xa且xb 或 xa且xc， 也即xab 或 xac ，即 xt，所以st （4分） 反之，若xt，则xab 或 xac， 即xa且xb 或 xa且xc 也即xa且xbc，即xs，所以ts 因此t=s （8分）2010年 7月一、单项选择题（每小题3分，本题共15分）1b 2d 3b 4c 5b1若集合a=1，2，1，2，则下列表述正确的是( ) a2a b1ac1a 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下列公式中 ( )为永真式aab ab bab (ab) cab ab dab (ab)二、填空题（每小题3分，本题共15分）6命题公式的真值是 假（或f，或0） 7若无向树t有5个结点，则t的边数为 4 8设正则m叉树的树叶数为t，分支数为i，则(m-1)i= t-1 9设集合a=1，2上的关系r,，则在r中仅需加一个元素 ，就可使新得到的关系为对称的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=，则f是a到b的函数14设g是一个有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 （8分）（3） a-（ab）=1, 2 （12分）17图g=，其中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与s是集合a上的自反关系，则rs也是集合a上的自反关系证明：设xa，因为r自反，所以x r x，即r； 又因为s自反，所以x r x，即s （4分） 即rs （6分） 故rs自反 （8分）2010年1月一、单项选择题（每小题3分，本题共15分）1a 2c 3b 4b 5d1若集合a a，a，则下列表述正确的是( ) aaa baaca，aa da2命题公式（pq）的合取范式是 ( ) a（pq） b（pq）（pq） c（pq） d（pq）3无向树t有8个结点，则t的边数为( )a6 b7 c8 d9 4图g如图一所示，以下说法正确的是 ( )aa是割点 bb, c是点割集cb, d是点割集 dc是点割集 图一5下列公式成立的为( )apq pq bpq pq cqp p dp(pq)q二、填空题