离散题库20套答案.doc

试题参考答案及评分标准离散1一、选择题（每题2分，共20分）CABBB DACDA二、填空题（每题2分，共20分）1. 2.ab=1，ab=0 3.x*(xy)=x x(x*y)=x 4. 无回路5. 大项的合取所组成 6. ($x) P(x) (x) P(x)7.68.对任意的a,b,有(a*b)*(a*b)=(a*a)*(b*b)9. 10. ，,，,三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1. (5分）给定无孤立点图G，若存在一条路，经过图中每边一次且仅一次，该条路称为欧拉路；如果一个图有欧拉路，则这个图能一笔画出。2. （8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)(PQR)主合取式:（PQR）（PQR）（PQR）3. （5分）由无向树的性质可知，无向树的顶点数是边数加1，又知无向图所有顶点的度之和为边数的2倍。（1分）令1度顶点个数为x,则顶点数为2+1+3+x，所有顶点的度之和为x+2*2+3+3*4，（2分）从而有x+2*2+3+3*4=2*(2+1+3+x-1)，解之得x=9,即有9个1度的点。（2分）4. （7分）解：5. （5分）（2分）,（2分）,具有自反，对称性质（1分）五、证明（3小题，共20分）1. （10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）PRP（2）RPT（1）E（3）PQP（4）PQT（3）E（5）QSP（6）PST（4）（5）I（7）RST（2）（6）I（8）RST（8）E2. （5分）。证明：(AB)(AC)=(AB)(AC)=A(BC)=A(BC)=A(BC)3. （5分）证明过程：明显，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)(PQ)(PQ)或（(PQ)(PQ)等）2.自反，反对称，传递3.（）4.经过图中每边一次且仅一次 5. 上确界 6.MaxMin+可结合性YYY可交换性YYY存在幺元NNN存在零元NNY7. 至少有两个元素的有补分配格 8. 小项的析取所组成 9. x | (xA) (xB) 10. 简单图中若每一对结点间都有边相连三、判断题（每题1分，共10分） 四、解答题（3小题，共20分）1. （5分）在根树中，若每一个结点的出度小于或等于2，则这棵树称为2叉树。任何一棵有序树都可以改写为对应的二叉树，方法是：除了最左边的分枝点外，删去所有从每一结点长出的分枝。在同一层次中，兄弟结点间用从左到右的有向边连接。选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上给定结点右邻结点，作为右儿子，以此类推。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:（PQR）（PQR）（PQR）主合取式:（PQR）（PQR）（PQR）（PQR）（PQR）3.（7分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成树建立通讯线路能使城市间直接通讯，按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。（1分）通讯方案（最小生成树）：（5分）最小总造价为：57（1分）五、证明（3小题，共30分）4. （10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）PQP（2）QRP（3）QRT(2)E（4）PRT(1)（3）I（5）RP（6）PT（4）（5）I（7）SPP（8）ST(6)（7）I5. （10分）证明过程：证明：因为R和S都是非空集A上的等价关系，所以R和S都有自反性，对称性和传递性。（1分）（1）,则,所以,所以RS是自反的。（2分）（2），则，因为R和S是对称的，所以（3分），从而,所以RS是对称的。（3），则，因为R和S是传递的，所以，从而,所以RS是传递的。（3分）由上面的三点可得RS是A上的等价关系。（1分）6. （6分）证明过程：如果图G(V,E)不连通的话，它的顶点可以分为两个非空集合A,B，其中对于任意在A中的点P和任意在B中的点Q都没有PQ这条边。（3分）取其补图，则对于任意在A中的点P和任意在B中的点Q都有PQ这条边。这样的话，对于任意两点P,Q，如果它们分别处于A,B的话，它们之间就有边相连；否则，不失一般性设它们都在A中，由于B非空，我们可以在B中任取一点R，我们知道PR和QR这两条边都是存在的，所以P,Q是连在一起的。综上，知连通。（3分）4（4分）证明过程：证明：显然，*运算封闭，且(a*b)*c=a*(b*c)=a+b+c-4,所以*满足结合律。（2分）2是幺元，4-a是a的逆元。所以是群。（2分）离散3一、选择题（每题2分，共20分）CCAAD DBDAB二、填空题（每题2分，共20分）1（1）PQ，（2）（PQ）(PQ)2.F3.不相等4.x和y的最大公约5.6.永真公式 给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式。 7. 经过图中每边一次且仅一次 8. |xXzZ($y)(yYRS) 9. G中的任意元素都由a的幂组成 10. 边界的回路长度三、判断题（每题1分，共10分） 四、解答题（4小题，共30分）1. （5分）设P是谓词（1）全称量词消去规则，简称US规则：(x)P(x)P(c) ，c为个体域中某个任意的客体； （2）全称量词引入规则，简称UG规则：P(x) (x)P(x)；（3）存在量词消去规则，简称ES规则：($x)P(x) P(c)，这里c是论域中的某些客体。（4）存在量词引入规则，简称EG规则：P(c) ($x)P(x)，这里c是论域中的一个客体。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)(PQR)3.（10分）哈斯图4分,其它各2分.R的哈斯图:集合A:最大元素为无、极大元素为24,36、下界为无、上确界为无。集合B:最大元素为12、极大元素为12、下界为2,3,6、上确界为12。集合C:最大元素为6、极大元素为6、下界为无、上确界为6。4.（7分）最优二叉树5分,最佳前缀码方案1分,编码信息1分解：根据字母出现的频率得出字母对应的最优二叉树和各字母的编码:传输它们的最佳前缀码方案:w:0000,p:0001,a:001,r:,y:011,h:10,e:110,n:111.happynewyear的编码信息:1000100010001011111110001010五、证明（3小题，共20分）1. （8分）每步约1.5分,没有P,T标识扣3分,没有序号扣3分。证明过程：(1)EP(2)EFT(1)I(3)(EF)DP(4)DT(2),(3)I(5)BDP(6)BT(4),(5)I2. （6分）证明过程：设平面图的结点数为v,边数为e,面数为r,则有欧拉公式成立：v-e+r=2.（1分）本题中，v=6,e=12,从而r=8.（1分）根据定理，所有面和次数之和为边数的2倍。而边数为12,所以8个面的次数之和为24.（1分）每个面的次数至少为3,要8个面的次数之和为24.每个面的次数只能为3.（2分）3. （6分）证明过程：证法（1）：证明在运算+上封闭性对于任意，设=2，=2， 则+=2+2=2（+） 说明在运算+上封闭。 (4分)又I 是的子群 (得2分)证法（2）：I 证明是一个群（1）封闭性： ，有=2，=2，+=2（+） (1.5分)（2）结合律： （+）+=2（+）=+（+） (1.5分)（3）幺元： +0=0+=0 0是幺元 (1.5分)（4）每一个元素都有逆元： x,由 x-x=0，得x的逆元为-x。(1.5分)离散4一、选择题（每题2分，共20分）CDACA DBABB二、填空题（每题2分，共20分）1.P Q，(PQ)(PQ)(或(PQ)(PQ),(PQ)2.2n3.4. 5.欧拉回路 6. *x=x*= 7. ($x)P(x) P(c) 8. IA 9. 良序集 10. V V ，E E三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1（5分）（1）置新矩阵A=M（2）置i=1（3）对所有j如果Aj, i =1，则对k=1,2,nAj,k=Aj,k+Ai,k（4）i= i+1（5）如果 i n,则转到步骤（3）,否则停止。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主合取式:PQR3（4分）U=a,b,c,d,e, A=a,d, B=a,b,c。求P(A)-P(B)解：P(A)=,a,d,a,d,P(B)=,a,b,c,a,b,a,c,b,c,a,b,c（2分）P(A)-P(B)=d,a,d（2分）4.（9分）解：(1) （4分）(2) 前缀码对应的二叉树T为（3分）前缀码：2：0001，3：0001，5：001，7：，8：011（2分）5. （4分）解：令ac=a,ad+b=b得，c=1,d=0,即幺元为 （2分）令*=得，ac=1,ad+b=0所以c=1/a, d=-b/a,从而-1= （2分）五、证明（2小题，共20分）7. （10分）每步约2分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）P(QR)P（2）R(QS)P（3）(QR)ST(2)E（4）(QR)(QS)T(3)E（5）P(QS)T(1)(4)I8. （10分）证明： aA则有a *a =ea*b=a*c *a*b=*a*c e*b=e*c b=c (4分)已知*e=e*e=e= 由的结论得 x*e=x,e是幺元 (2分)是半群,满足封闭性与结合律,则只需证明每一个元素都有逆元. =e*=*e又由的结论得 =x*=e x的逆元 为群 (4分)离散5一、选择题（每题2分，共20分）CADAC DBCBA二、填空题（每题2分，共20分）1（1）PQ，（2）（PQ）(PQ)2.F T3. a4，a5，a6，a7,a84. ,5.n-16.有零个或两个奇数度结点7.b*a=a*b=e8.P(c) ($x)P(x) 9.对于每一个xX,有唯一的yY，使得f10.图G的子图G包含G的所有结点三、判断题（每题1分，共10分） 四、解答题（5小题，共3029分）1（5分）若把一个集合A分成若干个非空子集，使得A中每个元素属于且仅属于一个分块，这些分块的全体叫做A的一个划分。设A的一个划分为：，则就是由这个划分确定A的元素间的一个等价关系。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)(PQR)(PQR)3（4分）解：A-B=d,B-C=a,c(2分)(A-B)(B-C)= a,c,d(2分)4.（7分）解：八进制数字出现的频率已从小到大排列,由这些频率求出最优二叉树为下右图，： 由最优二叉树树叶对应最优前缀码：.(2分) (3分)各八进制数字对应最优前缀码为:7:0001,6:0000,5:1111,4:1110,3:110,2:001,1:10,0:01 (2分)5.（6分）解：这是一个顶点着色问题的应用。将顶点的度从大到小排列得到：v3:6,v9:5,v7,v8:4,v1,v2,v4,v5,v6:3。将v3着颜色1,v9着颜色2，v7着颜色1,v8着颜色3,v1着颜色2,v2着颜色3,v4着颜色2,v5着颜色1,v6着颜色2,因而图是3可着色的。即可以用3天考完所有考试。将v9着颜色1,v3,v7着颜色2，v1着颜色1,v2着颜色3,v4着颜色1,v5着颜色2,v6着颜色1,因而图是3可着色的。即可以用3天考完所有考试。五、证明（2小题，共20分）4. （10分）每步约1.5分,没有P,T标识扣3分,没有序号扣3分。证明过程：(1) RSP(2)SRT(1)E(3)PRP(4)RPT(3)E(5)PQP(6)RQT(4),(5)I(7)SQT(2)(6)I5. （10分）证明过程：要证明R是自反的，对称的和传递的，R才是等价关系。（1分）（1）,因为a+b=a+b,所以，所以R是自反的。（2分）（2），则从而，所以R是对称的。（2分）（3），则a+d=b+c,c+f=d+e,将上式左右相加得a+f=b+e,即,所以R是传递的。（2分）综上所述，R是等价关系。（1分）R是一个等价类集合，由和有关系的元素构成。（1分）R=,（1分）离散6一、选择题（每题2分，共20分）DACBC ADCBD二、填空题（每题2分，共20分）1.PQ，(PQ)(PQ)(或(PQ)(PQ),(PQ)2.P=T，Q=F3.A的覆盖有S1，S2，S3，S4，S5，A的划分有S3，S4，S54.b5.，n-16.所有结点度数为偶数7. ，8.IA9.对于所有xA和 xC有f(x)=g(x) 10.若存在一条路三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1（5分）哈斯图是简化的偏序关系图，具体画法如下：（1）用小圆圈代表元素；（2）若x y，x y，将代表y的小圆圈放在代表x的小圆圈之上，（3）如果 COVA，则在y与x之间用直线连接。2.（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)(PQR)(PQR)(PQR)3.（6分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成树建立通讯线路能使城市间直接通讯，按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。（2分）通讯方案（最小生成树）：（3分）最小总造价为：18（1分）4.（7分）如果前缀码是其它的方案，只要思路正确，也给满分。解：H：000，A：001，P：，N：011，E：100，W：101，R：110，Y：111（2分）该前缀码对应的二叉树：（3分）英文短语HAPPYNEWYEAR的编码信息：000001010010111011100101111100001110（2分）5（4分）直接写出结果给2分解：AB=b,c,d,(AB)C=b,d五、证明（2小题，共20分）9. （10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）A P(附加前提)（2）AB T I（3)ABCD P（4)CD T(2)(3) I（5)D T(4) I（6)DE T(5) I（7)DEF P（8)F T(6)(7) I（9)AF CP10. （10分）证明过程：（1）对于任意a,bR-1若a*b=a+b+ab=-1，则有a=(-1-b)/(1+b)=-1，与a R-1矛盾。*运算满足封闭性 （2分）（2）对于任意a,b,cR-1有 (a*b)*c=(a+b+ab)*c=a+b+ab+c+(a+b+ab)c =a+b+c+ab+ac+bc+abc 而a*(b*c)=a*(b+c+bc)=a+b+c+bc+a(b+c+bc) =a+b+c+bc+ac+ab+abc (a*b)*c=a*(b*c)*运算满足结合性 （2分）（3）设对任意元素aR-1，则有a*0=a+0+a0=a0*a=0+a+0a=a即有 a*0=0*a=a 0是幺元 （2分）（4）对于任意a,bR-1设a*b=a+b+ab=0，则有b(1+a)=-ab=-a/(1+a)也就是a(-a/(1+a)=0这说明任意aR-1,a有逆元-a/(1+a)。（3分）由于中*运算封闭，满足结合律，有幺元，任意元素有逆元，所以是群离散7一、选择题（每题2分，共20分）BDCAB CADBC二、填空题（每题2分，共20分）1（1）PQ，（2）（PQ）(PQ) 2.T3.C4.k5.每条边一次且仅一次6.经过图中的每一个结点恰好一次7.封闭的和可结合的8.A1 A2 An，（n1）其中A1，A2 ，An都是由命题变元或其否定所组成的析取式。9.x*y=y*x10.图G=V,E的任意两个结点皆有路连通三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1（5分）若把一个集合A分成若干个非空子集，使得A中每个元素属于至少属于一个分块，这些分块的全体叫做A的一个覆盖。设A的一个覆盖为：，则就是由这个划分确定A的元素间的一个相容关系。2（3分）解：=0,2(1分)R=,(2分)3（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)(PQR)(PQR)4.（10分）解：关系矩阵:关系图: （4分）求的传递闭包t(R)有二种矩阵运算方法：（1）矩阵幂方方法：，所以（4分）(2)Warshall方法：所以（4分）的传递闭包t(R)= , （2分）5.（6分）解：这是一个顶点着色问题的应用。（1分）将顶点的度从大到小排列得到：v9:5,v3:4,v7,v4:4,v1,v2,v5,v8,v6:3。（2分）将v9着颜色1,v3,v7着颜色2，v4着颜色1,v1着颜色1,v2着颜色3,v5着颜色2,v8着颜色3,v6着颜色3,因而图是3可着色的。（2分）即可以用3天考完所有考试。（1分）五、证明（2小题，共20分）1. （10分）每步约1.5分,没有P,T标识扣3分,没有序号扣3分。证明过程：(1)BDP(2)BDT（1）E(3)(CA)DP(4)D(CA)T（3）E(5)B(CA)T（2）（4）I(6)B(CA)T（2）（4）I(7)（BC）（BA)T（5）E(8)BCT(6)I2. （10分）证明过程：（1）对任意A,由于xy=yx，有,R所以R具有自反性。（3分）（2）对任意，R,有xv=yu，即uy=vx从而有，R所以R具有对称性。（3分）（3）对任意，R，R,有xv=yuuz=vw,xz=yw,由定义得，R所以R具有传递性。（3分）由于R具有自反性，对称性和传递性，所以R是等价关系。（1分）离散8一、选择题（每题2分，共20分）ABCDD BDACA二、填空题（每题2分，共20分）1（1）P Q （2）PQ 2.T 3.a b c d 4. n-15.经过图中的每一个结点恰好一次6.幺元7. (x)(xAxB) 8.RIA9.x*yA10.单侧三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1（5分）（1）关于R的全体不同的等价类为元素的集合 aR| aA称为A关于R的商集，记为A/R。（3分）（2）把彼此有关系的元素放在一个集合中，由这些集合组成一个集合就是关于R的商集。（2分）2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)(PQR)(PQR)(PQR)3（10分）解：关系矩阵:关系图: （4分）求的传递闭包t(R)有二种矩阵运算方法：（1）矩阵幂方方法：，所以（4分）(2)Warshall方法：所以（4分）的传递闭包t(R)=,（2分）4.（3分）解：R=, (3分)5.（4分）解：RR=, （2分）Rc=,（4分）五、证明（3小题，共20分）3. （8分）每步约1.5分,没有P,T标识扣3分,没有序号扣3分。证明过程：（1）R P（2） QR P （3） Q T（1）(2) （4） (PQ) P（5） PQ T(4)E（6） P T(3)(5)I4. （6分）最优树为：（3分）W（T）=(1+2+1+1)4+(2+3)3+(4+5)2=53（3分）5. （6分）证明：有,使得,对,有,使得因而*e)=()*e=e*e=e= (3分)上式左边同时乘以得()*(x*e)=()*x即e*(x*e)=e*x,也就是x*e=x e是右幺元,从而e是幺元。 离散9一、选择题（每题2分，共20分）ACBDD AACAB二、填空题（每题2分，共20分）1.2. 3. b4.具有汉密尔顿回路5.（1）运算*是封闭的。（2） 运算*是可结合的。（3） 存在幺元e。（4） 对于每一个元素xG,存在着它的逆元x-16.析取式中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。7.若AB,且BC, 则AC8.RRc9.(x*y)*z=x*(y*z)10. 强连通图三、判断题（每题1分，共10分）四、解答题（5小题，共29分）1（5分）封闭性：A中的每个元素都在运算表中；可交换性：运算表关于主对角线是对称的；等幂性: 运算表中主对角线中的元素等于它所在行和列的表头元素；零元：该元素所在行和所在列的元素值都与该元素相同；幺元: 该元素所在的行和列依次与运算表中的行和列相同。 2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。主析取式：(PQR)(PQR)(PQR)(PQR)(PQR)主合取式：(PQR)(PQR)(PQR)3（4分）RR的关系矩阵（2分）R-1的关系矩阵:（2分）4（8分）(6分)W(T)=2*4+3*4+5*3+9*2+7*2+8*2=83(2分)5.（5分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成树建立公路能使城市间有公路连通，按最小生成树建立公路能使城市间有公路连通且总造价最小。（1分）最优化的设计方案:（4分）公路长：9（1分）五、证明（3小题，共24分）1（10分）每步约1.5分,没有P,T标识扣3分,没有序号扣3分。证明过程：证法1 （1） P（2）T(1)E（3)P（4)T(3)E（5)T(2)(4)I（6)P（7)T(5)(6)I法2 （1）P(附加前提)（2）P（3)T(2)E（4)QT(1)(3)I（5)P（6)RT(4)(5)I（7)P（8)ST(6)(7)I（9)CP2（10分）（1） （1分）（2）r(R)=RIA=, （2分）S(R)=RRc=, （2分）t(R)=RR2R3R4=,，, （3分） 也可用Warshall算法计算t（R）。（3）包含R的最小的等价关系=r(R)S(R)t(R)=,，,IA离散10一、选择题（每题2分，共20分）AABCD CBDCB二、填空题（每题2分，共20分）1（1）P Q，（2）（PQ）(PQ) 2.a ca b3.2,4 和4.e=v-15.任何两条边除了端点外没有其它的交点6.ab-1S7. 对任意素数x，总存在奇数y，使得y可以整数 8.RR2R39.x*(yz)=(x*y)(x*z) (yz)*x=(y*x)(z*x) 10.弱连通的三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1（5分）设是一个代数系统，其中G是非空集合，*是G上一个二元运算，如果（1） 运算*是封闭的。（2） 运算*是可结合的。（3） 存在幺元e。（4） 对于每一个元素xG,存在着它的逆元x-1。则称是一个群。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:( PQR)(PQR)(PQR)主合取式:( PQR)(PQR)(PQR)(PQR)(PQR)3（4分）解：P(A)=(2分)P(A)A=,(2分)4.（5分）解：R=,（2分）RR=,（2分）R-1=,（1分）5.（8分）若传递a ，b， c， d ，e， f 的频率分别为2%， 3% ，5 %， 7% ，8% ，9%求传输它的最佳前缀码。解：这是一个求最优二叉树问题。（1分）频率最优二叉树（3分）字符最优二叉树（2分）最佳前缀码：a:0000,b:0001,c:001,d:01,e:10,f:11（2分）五、证明（3小题，共20分）6. （8分）每步约0.8分,没有P,T标识扣3分,没有序号扣3分。证明过程：(1)AP(附加条件)(2)A(BC)P(3)BCT（1）（2）I(4)(CD)EP(5)G(DE)P(6)(CD)ET(4)E(7)C(DE)T(6)E(8)(DE)GT（5）E(9)CGT(7)(8)I(10)BGT(3)(9)I(11)A(BG)CP7. （8分）证明过程：证明：充分性证明：设对任意有因为 所以即得：因此，群是阿贝尔群。（4分）必要性证明：设是阿贝尔群，则对任意有，因此 （4分）8. （4分）证明过程：解：a的等价类aR =a,b （2分）A/R=a,b，c，d，e,f （2分离散11一、选择题（每题2分，共20分）BACDB ACACD二、填空题（每题2分，共20分）1. 所有子集为元素 2. S1S2 SmA 3. x (xB y x) 4. 可交换的 5. 不含有平行边和环的图 6. 结点 边 7PQ （PQ）(QP）8. SiSj=，（这里ij）9.10.三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）6. （5分）设A ，R A A，若R是自反的、反对称的和传递的，则称R是A上的偏序关系。设为偏序集，BA，若存在yB，使得x (xB x y)为真，则称y为B的最大元；若存在yB，使得x (xB y x x = y)为真，则称y为B的极大元。7. （8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)8. （7分）解：9. （5分）（2分）,（2分）,具有自反，对称性质（1分）10. （5分）3个2度顶点、1个3度顶点、2个4由无向树的性质可知，无向树的顶点数是边数加1，又知无向图所有顶点的度之和为边数的2倍。（1分）令1度顶点个数为x,则顶点数为3+1+2+x，所有顶点的度之和为x+3*2+3+2*4，（2分）从而有x+3*2+3+2*4=2*(3+1+2+x-1)，解之得x=7,即有7个1度的点。（2分）五、证明（3小题，共20分）11. （10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）PRP（2）RPT（1）E（3）PQP（4）PQT（3）E（5）QSP（6）PST（4）（5）I（7）RST（2）（6）I（8）RST（8）E12. （5分）。证明：“”必要性：已知CA，即xC，则有xA，此时有AC=A (AB) C=(AC) (BC)=A (BC) （2.5分） “” 充分性： 已知(AB) C=A (BC） 设任意的xC，则xC(AB) xA(BC) xA CA （2.5分）13. （5分）证明过程：明显，H是G的子集。任取xH,则有ax=xa，对等式左乘和右乘x-1,有x-1a=ax-1.再任取yH,则(yx-1)a=y(x-1a)=y(ax-1)=(ya)x-1=(ay)x-1=a(yx-1)由定理可得，H是G的子群。离散12一、选择题（每题2分，共20分）CCABD BBDCA二、填空题（每题2分，共20分）1.a,b2. 3.SS45. x*x=x 6. ， 7. 假设A为T时，说明B也为T。假设B为F时，说明A也为F。8. 如果对于任意的x,y,zA, 每当xRy， yRz 时就有xRz 或(x)(y)(z)(xAyAzAxRy yRz xRz) 9. (a*b)*(a*b)=(a*a)*(b*b) 10. 诸边所构成的回路三、判断题（每题1分，共10分） 四、解答题（3小题，共20分）1（5分）哥尼斯堡七桥问题：哥尼斯堡城市有一条横贯全城的河，河中有二个小岛，河二岸与第一个小岛各用二座桥连接，河二岸与第二个小岛各用一座桥连接，小岛与小岛用二座桥连接。每逢假日，城中的居民进行环城的逛游，这样就产生一个问题，能不能设计一次“逛游”，使得从某地出发对每座跨河桥走一次，而在遍历了七桥之后却又能回到原地。哥尼斯堡七桥问题没有解，因为该问题可以变为判别一个有4个顶点7条边的连通图是不是欧拉图，由于该图不是每个顶点的度都是偶数，所以不是欧拉图。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取式:(PQR)(PQR)(PQR)(PQR)主合取式:(PQR)(PQR)(PQR)(PQR)3.（7分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成树建立通讯线路能使城市间直接通讯，按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。（1分）通讯方案（最小生成树）：（5分）最小总造价为：57（1分）五、证明（4小题，共30分）14. （10分）每步约1分，没有P,T标识扣3分,没有序号扣3分。证明过程：（1）PQP（2）QRP（3）QRT(2)E（4）PRT(1)（3）I（5）RP（6）PT（4）（5）I（7）SPP（8）ST(6)（7）I15. （10分）证明过程：证明：因为R和S都是非空集A上的等价关系，所以R和S都有自反性，对称性和传递性。（1分）（1）,则,所以,所以RS是自反的。（2分）（2），则，因为R和S是对称的，所以（3分），从而,所以RS是对称的。（3），则，因为R和S是传递的，所以，从而,所以RS是传递的。（3分）由上面的三点可得RS是A上的等价关系。（1分）16. （4分）证明过程：A(BC)A(BC)(AB)(AC)=(AB)(AC)=(AB)(AC)=(ABA)=(ABC)所以A(BC)(AB)(AC)。明显，H是G的子集。5（6分）证明过程：证明：显然，*运算封闭，且(a*b)*c=a*(b*c)=a+b+c-4,所以*满足结合律。（3分）2是幺元，4-a是a的逆元。所以是群。（3分）离散13一、选择题（每题2分，共20分）BACDA CBDAC二、填空题（每题2分，共20分）1.s（R）=，,，2.a1,a2,a3,a4,a5或a4,a5,a6,a7,a8,=3.是一个群.4.连通且每个结点的度数为偶数.5.自反的、对称的和传递的 6. e*x=x*e=x 7. 主析取 8. x | (xA) (xB) 9. x z z y 10. 为n(n-1)/2三、判断题（每题1分，共10分） 四、解答题（5小题，共30分）1（5分）图G的正常着色(或简称为着色)是指对它的每一个结点指定一种颜色，使得没有两个相邻的结点有同一种颜色。韦尔奇鲍威尔法(Welch Powell)对图进行着色的方法：将图G的结点按照度数的递减次序进行排列。(这种排列可能并不是唯一的，因为