资源描述：
《离散题库20套答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、—、选择题（每题2分，共20分）CABBBDACDA二、填空题（每题2分，共20分）2.日/戻03.x*(xAy)=xxA(x*y)=x4.无回路5.大项的合取所组成6.(3x)-1P(x)(Vx)-iP(x)7.68.对任意的8,G，有(a*b)*(a*b)=(a*a)*(b*b)9.BY10.{<1,2>,<3,3>,<1,3>,<4,2>},{<1,4>,<2,2>}三、判断题（每题1分，共10分）XVVXXXXXVV四、解答题（5小题，共30分）1.（5分）给定无孤立点图G,若存在一条路，经过图中每
2、边一次且仅一次，该条路称为欧拉路；如果一个图有欧拉路，则这个图能一笔画出。2.（8分）各4分，步骤对，结果错，适当扣分，如杲求出其一个，另一个直接写出，也不扣分。只有结果,且结果对，给一半分，只有结果，且结果错，不给分。解：主析取范式：GPA-iQAR）V（nPA-iQA-iR）V（PAQAR）V（PAnQAR）V（nPAQAR）主合取范式：（「PVQVR）A（nPV-iQVR）A（PVqQVR）3.（5分）由无向树的性质可知，无向树的顶点数是边数加1,又知无向图所有顶点的度之和为边数的2倍。（1分）令1度顶
3、点个数为x,则顶点数为2+1+3+x,所有顶点的度之和为x+2*2+3+3*4,（2分）从而有x+2*2+3+3*4二2*（2+l+3+x-l）,解之得x二9,即有9个1度的点。（2分）<100110(5分)Mr=101（0015.0、0（2分），具有自反，对称性质（1分）五、证明（3小题，共20分）1.（10分）每步约1分，没有P,T标识扣3分，没有序号扣3分。证明过程:(1)P-RP(2)-iRf-iPT(1)E(3)PVQP(4)「P-*QT(3)E(5)Q-SP(6)—iP->ST(4)(5)I(7)
4、「RfST(2)(6)I(8)RVST(8)E2.（5分）。证明：(A-B)u(A-C)=(An~B)U(An~c)=Ac(〜Bu~c)=Ac~(BcC)=A-(BcC)3.(5分)证明过程：明显，H是G的子集。任取xGH,则有a*x=x*a,对等式左乘和右乘x-1,有x_1*a=a*x_1.再任取yGH,则(y*x')*a二y*(x**a)=y*(a*x!)=(y*a*)x,=(a*y)*xl=a*(y*x')由定理可得，II是G的子群。或由群的定义来证明。离散2—、选择题（每题2分，共20分）BCCADA
5、ABDC二、填空题（每题2分，共20分）1.（1）PQ（2）GPVQ）A（PV-iQ）或（GPA-iQ）V（PAQ）等）2.自反，反对称，传递3.iAOiB（或4.经过图中每边一次且仅一次5.上确界6.MaxMin+可结合性YYY可交换性YYY存在幺元NNN存在零元NNY6.至少有两个元素的有补分配格7.小项的析取所组成8.x
6、（xgA）a（xeB）9.简单图中若每一对结点间都有边相连三、判断题（每题1分，共10分）XXVVXVVXXV四、解答题（3小题，共20分）1.（5分）在根树中，若每一个结点的出度小于
7、或等于2,则这棵树称为2叉树.任何一棵有序树都可以改写为对应的二叉树，方法是：⑴除了最左边的分枝点外，删去所有从每一结点长出的分枝。在同一层次中，兄弟结点间用从左到右的有向边连接。⑵选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上给定结点右邻结点，作为右儿子，以此类推。2.（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果,且结果对，给一半分，只有结果，且结果错，不给分。解：主析取范式：（iPaQaR）V（-1Pa-]QaR）V
8、（PaQaR）主合取范式：（-]PVQX/R）a（-!PVQV-iR）a（PVQVR）a（PVnQVR）a（nPVnQVR）1.（7分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成树建立通讯线路能使城市间直接通讯，按最小牛成树建立通讯线路能使城市间直接通讯冃总造价最小。（1分）通讯方案（最小生成树）:(5分)最小总造价为：57（1分）五、证明（3小题，共30分）4.（10分）每步约1分，没有P,T标识扣3分，没有序号扣3分。证明过程:(1)P-QP(2)->QVRP(3)Q-
9、*RT(2)E(4)P-*RT(l)(3)I(5)-iRP(6)—iPT(4)(5)I(7)->SVPP(8)-!ST(6)(7)T5.（10分）证明过程：证明：因为R和S都是非空集A上的等价关系，所以R和S都有白反性，对称性和传递性。（1分）（1）VxgA,则/?A€Sy所以所以RAS是自反的。（2分）（2）Vg/?nS,则v>wR/v兀,yS,因为R和S是对称的，所以（3分）
