离散数学试卷及答案三(4页).doc

《离散数学试卷及答案三(4页).doc》由会员分享，可在线阅读，更多相关《离散数学试卷及答案三(4页).doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-离散数学试卷及答案三-第 4 页一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列各图是平面图的是( ) 2.设G是n个顶点的无向简单图，则下列说法不正确的是 )A.若G是树，则其边数等于n-1B.若G是欧拉图，则G中必有割边C.若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点D.若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路不含与下面哪一个选项同构的子格( )4.设是有限循环群，则下列说法不正确的是( )A.的生成元是唯一的B.有限循环群中的运算*适

2、合交换律C.G中存在一元素a，使G中任一元素都由a的幂组成D.设a是的生成元，则对任一正整数i，存在正整数j使a-i=aj5.在实数集合R上，下列定义的运算中是可结合的只有( )A.a*b=a+2bB.a*b=a+b-2abC.a*b=a-b+2abD.a*b=a-b-2ab6.设群G=中,A的元素个数大于1，若元素aA的逆元素为bA，则a*b的运算结果是( )7.非空集合A上的二元关系R若是自反和对称的，则R是( )8.下面的图是A=1,2,3上关系R的关系图G(R),从G(R)可判断R所具有的性质是( )1。2。 3。A.自反，对称，传递B.反自反，非对称C.反自反，对称，非传递D.反自反

3、，对称，反对称，传递9.设A=1，2，3，B=a,b，下列二元关系R为A到B的函数的是( )A.R=,B.R=,C.R=,D.R=,为空集，P(x)是集合x的幂集，下列论断不正确的是( )A. P(), P()B.P（），P（）C. P（P（），P（P（）D.P（P（）,P（P（）11.利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：改写成( )A. B. C. D. 12.设论域为整数集，下列谓词公式中真值为假的是( )A.B. C. D. 13.在命题演算中，语句为真为假的一种性质称为( )14.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为(

4、)A.B. C. D. 15.下列命题公式是永真式的是( )A. qB.C. D.二、填空题(本大题共10小题，每空1分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.一棵有6个叶结点的完全二叉树，有_个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_个叶结点。17.在一棵根树中，有且只有一个结点的入度为_，其余所有结点的入度均为_。18.设是格，其中一个命题P是a(ab) (ac),则P的对偶命题是a_(ab)_(ac)。19.设Z是整数集，+是整数加法运算，则是群，其幺元是_，对任一整数i,其逆元是_。20.当f:XY是_

5、函数时，f有逆函数，且f -1。f=_。21.设E=1,2,3,4,5,6,A=1,4,B=1,2,3,C=2,4,则(AB)C=_,幂集P(AB)C)=_。22.设论域D=a,b,则(x)P(x)_,(x)(y)Q(x,y)_。23.使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x。24.由命题变元及其否定所组成的有限个析取式的合取式称为_，由命题变元及其否定所组成的有限个合取式的析取式称为_。25.不包含_的命题叫做原子命题，包含_的命题称为复合命题。三、计算题(本大题共7小题，第26、28小题每小题5分，第27、31小题每小题7分，第29

6、、30小题每小题8分，第32小题9分，共49分)26.用等值演算法，求P(QR)的主析取范式，并按P，Q，R顺序，写成编码形式。27.设A=1,2,3，给定A上二元关系R=,，求r(R),s(R)和t(R)。的前束范式。29.对如下有向图D，求D中长度为4的路有多少条?其中回路有多少条?30.设A=a,abc,bc,bcd,bd，定义A上二元关系R=|x,yA且字符串x包含于字符串y中，即R=IA,，可以验证R是A上偏序关系。作出R的哈斯图向R中最少添加几个序偶可使之成为等价关系?求出该等价关系所确定的集合A的划分。31.某科研所要从3个项目A、B、C中选择12个项目上马，由于某种原因，立项时

7、要满足以下条件：(1)若A上，则C也要上；(2)若B上，则C不能上；(3)若C不上，则A或B可以上。请找出所有的立项方案1，V2，V6，它们之间有输油管连通，其布置如下图(a),Si(数字)中Si为边的编号，括号内数字为边的权，它是两城市间的矩离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守管道的最短的总长度。(要求写出求解过程)四、证明题(本大题共2小题，每小题8分，共16分)33.证明(x) (P(x) Q(x)(x)P(x)(x)Q(x)34.证明当每个结点的度数大于等于3时，不存在有7条边的连通简单平面图。