离散数学题库.doc

离散数学题库.doc

ID:54226949

大小:3.51 MB

页数:34页

时间:2020-04-14

离散数学题库.doc_第1页
离散数学题库.doc_第2页
离散数学题库.doc_第3页
离散数学题库.doc_第4页
离散数学题库.doc_第5页
资源描述:

《离散数学题库.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、试题参考答案及评分标准离散1一、选择题(每题2分,共20分)CABBBDACDA二、填空题(每题2分,共20分)1.2.a∨b=1,a∧b=03.x*(xΔy)=xxΔ(x*y)=x4.无回路5.大项的合取所组成6.($x)ØP(x)("x)ØP(x)7.68.对任意的a,b,有(a*b)*(a*b)=(a*a)*(b*b)9.βγ10.{<1,2>,<3,3>,<1,3>,<4,2>},{<1,4>,<2,2>}三、判断题(每题1分,共10分)×√√×××××√√四、解答题(5小题,共30分)1.(5分)给定无孤立点图G,若存在一条路,经过图中每边一次且仅一次,该条路称

2、为欧拉路;如果一个图有欧拉路,则这个图能一笔画出。2.(8分)各4分,步骤对,结果错,适当扣分,如果求出其一个,另一个直接写出,也不扣分。只有结果,且结果对,给一半分,只有结果,且结果错,不给分。解:主析取式:(┐P∧┐Q∧R)∨(┐P∧┐Q∧┐R)∨(P∧Q∧R)∨(P∧┐Q∧R)∨(┐P∧Q∧R)主合取式:(┐P∨Q∨R)∧(┐P∨┐Q∨R)∧(P∨┐Q∨R)3.(5分)由无向树的性质可知,无向树的顶点数是边数加1,又知无向图所有顶点的度之和为边数的2倍。(1分)令1度顶点个数为x,则顶点数为2+1+3+x,所有顶点的度之和为x+2*2+3+3*4,(2分)从而有x+

3、2*2+3+3*4=2*(2+1+3+x-1),解之得x=9,即有9个1度的点。(2分)4.(7分)解:5.(5分)(2分),(2分),具有自反,对称性质(1分)34试题参考答案及评分标准五、证明(3小题,共20分)1.(10分)每步约1分,没有P,T标识扣3分,没有序号扣3分。证明过程:(1)P→RP(2)R→PT(1)E(3)PQP(4)P→QT(3)E(5)Q→SP(6)P→ST(4)(5)I(7)R→ST(2)(6)I(8)RST(8)E2.(5分)。证明:(A-B)(A-C)=(A~B)(A~C)=A(~B~C)=A~(BC)=A-(BC)3.(5分)证明过程:

4、明显,H是G的子集。任取xH,则有a*x=x*a,对等式左乘和右乘x-1,有x-1*a=a*x-1.再任取yH,则(y*x-1)*a=y*(x-1*a)=y*(a*x-1)=(y*a*)x-1=(a*y)*x-1=a*(y*x-1)由定理可得,H是G的子群。或由群的定义来证明。离散2一、选择题(每题2分,共20分)BCCADAABDC二、填空题(每题2分,共20分)1.(1)PQ(2)(┐P∨Q)∧(P∨┐Q)或((┐P∧┐Q)∨(P∧Q)等)2.自反,反对称,传递3.()4.经过图中每边一次且仅一次5.上确界6.MaxMin+可结合性YYY可交换性YYY存在幺元NNN存

5、在零元NNY7.至少有两个元素的有补分配格8.小项的析取所组成9.x

6、(xÎA)Ù(xÎB)10.简单图中若每一对结点间都有边相连三、判断题(每题1分,共10分)××√√×√√××√四、解答题(3小题,共20分)1.(5分)在根树中,若每一个结点的出度小于或等于2,则这棵树称为2叉树。任何一棵有序树都可以改写为对应的二叉树,方法是:⑴除了最左边的分枝点外,删去所有从每一结点长出的分枝。在同一层次中,兄弟结点间用从左到右的有向边连接。⑵选定二叉树的左儿子和右儿子如下:直接处于给定结点下面的结点,作为左儿子,对于同一水平线上给定结点右邻结点,作为右儿子,以此类推。2.(8分)

7、各4分,步骤对,结果错,适当扣分,如果求出其一个,另一个直接写出,也不扣分。只有结果,且结果对,给一半分,只有结果,且结果错,不给分。34试题参考答案及评分标准解:主析取式:(┐PQR)∨(┐P┐QR)∨(PQR)主合取式:(┐P∨Q∨R)(┐P∨Q∨┐R)(P∨Q∨R)(P∨┐Q∨R)(┐P∨┐Q∨R)3.(7分)这是一个求最小生成树的问题,可用多种方法,但必须有思路和过程。解:按该图的生成树建立通讯线路能使城市间直接通讯,按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。(1分)通讯方案(最小生成树):(5分)最小总造价为:57(1分)五、证明(3小题,共30分

8、)1.(10分)每步约1分,没有P,T标识扣3分,没有序号扣3分。证明过程:(1)P→QP(2)QRP(3)Q→RT(2)E(4)P→RT(1)(3)I(5)RP(6)PT(4)(5)I(7)SPP(8)ST(6)(7)I2.(10分)证明过程:证明:因为R和S都是非空集A上的等价关系,所以R和S都有自反性,对称性和传递性。(1分)(1),则,所以,所以RS是自反的。(2分)(2),则,因为R和S是对称的,所以(3分),从而,所以RS是对称的。(3),则,因为R和S是传递的,所以,从而,所以RS是传递的。(3分)由上面的三点可

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。