资源描述：
《离散结构试卷答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、离散结构2(X)7-a一、填空(每空2分，共30分)1、设P：2+2=4,Q：3是奇数将命题“2+2-4,当且仅当3是奇数”符号化_(1)_,其真值为_(2)_。2、在公式玉(尸(兀，刃)中，自由出现的变元为—(3)_。3、若关系R具冇自反性，当且仅当在关系矩阵屮，主对角上元素_(4)—,若关系R具冇对称性，当且仅当关系矩阵是_(5)—o4、若关系二R,则关系尺一定具有_(6)_性。5、有向图的连通性可分为弱连通、強连通、_(7)—o6、前缀表达式+*2/843的值是_(8)—。7、设G是完全二元树，G有15个顶点，其中有8个叶子，则6有_(9)—条边，G的总度数是_(10)—。8、十进
2、制3位数的数字屮恰好冇一个8和一个9,共冇_(11)—个这样的3位数。9、设集合S={a,b,c,d,e}fS上的运算*定义为:10、设vS,*>是由元素aeS生成的循环群，且S的阶为4,则集合S=_(15)二、选择题(每题2分，共30分)1、下列语句中，是命题。A、地球上的人克多B、把门关上C、下午有会吗？D、x+5>62、一个公式在等价意义下，下而哪个写法是唯一的oA、析取范式B、合取范式C、主析取范式D、以上都不唯一3、设命题公式—「(戸―。)人Q,则&是oA、永真式B、矛盾式C、可满足式D、以上都不是4、设/是如下一个解释，D={a,b},其中p(a,a),p(b,a)为真，p(
3、a,b),p(b,b)为假，贝恠解释1下取真值的公式是d、y)a、3x/yp(x,y)b、/x^/yp(x,y)c、x)5、下列哪个表达式错误A、3x(P(x)/Q(x3xP(x)/3xQ(x)B、VxP(%)vX/xQ(x)nVx(P(x)vQ(x))c、3x(P(x)v2(x))03xP(x)v3xQ(x)d、Vx(P(x)v0(兀))o/xP(x)vVxg(x)6、设/?,s是集合A={1,2,3,4}上的两个关系，其中R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>}，则s是/?的闭包。7、A、自反
4、B、反对称C、对称D、传递设/?和S是非空集合4上的等价关系,下列各式是A上等价关系的是A、AxA-Rb、R—Sc、RoSd、R-S的对称闭包8、设偏序集(vA<>)关系r的哈斯图如右所示，若a的子集B={2,345}，则元素6为3的9、C.最小上界D>以上都不对以下整数序列，能成为一个简单图的顶点度数序列的是A、1,2,2,3,4,5B、2,3,3,4,4,5C、1,1,1,2,3D、2,3,3,4,5,6410、设图G是有6个顶点的连通图，总度数为20.则从G屮至少删去条边后使Z成为树。D、A、1()B、5C、311、在下列关于图论的命题中，正确的是。A.哈密顿图一定是欧拉图B、无向
5、完全图Kit(n>3)都是欧拉图C、度数为奇数的顶点个数为0个或2个的连通无向图可一笔画出D、哈密顿图是平面图12、下面编码不是前缀码。A、11,00,10,01B、01,11,011,1001C、101,11,001,011,010D、010,11,011,1011,100L1010113、5阶非同构的无向树有棵。A、1B、2C、3D、414、由0、1、2、3这四个数字能构成个3位数A、64B、48C、24D、1815、在下列选项中，不是群的是。A、(0,+)，Q为有理数，+为加法运算B、为非零实数集，。为乘法运算C、全体实对称矩阵集合，对于矩阵的加法运算D、(Q,*)，Q为有理数为乘
6、法运算三、计算题(5分+5分+8分，共18分)1、设冇5个城市V,,V2,V3,V4,V5,任童两城市Z间的铁路造价如下：Wpv2)=4,WPv3)=7,W(VpV4)=16,WPv5)=10,叫宀)=13,W(v2,v4)=8,W(v2,v5)=7,叫宀)=3,W(v3,v5)=5,W(v4,v5)=12试求出连接5个城市的且造价最低的铁路网2、构造前序遍历为a,b,f,c,g,h,i,d,e,j,k,卩的有序树，其中a有4个子结点，c•有3个子结点，/有2个了结点，b和e都有一个了结点，所有其它结点都是树叶。34、设集合A={1,2,3,4,5},A上的关于等价关系的商集A//?={
7、{1,2,3},{4,5}},试求:(1)等价关系R(2)写出关系矩阵Mr(1)画出关系图(2)写出/?的传递闭包四、证明题(5分+5分+6分，共16分)1、设/?是A上的等价关系，S是B上的等价关系，且A和3非空，关系7,满足：«x.a>,gR且wS,证明T是AxB上的等价关系。2、设G为”阶无向简单图，证明：若G为自补图(若一个图的补图为本身则称为自补图)，则n=4k或n=4k+,其中R为正
