《离散题库20套答案.doc》由会员分享，可在线阅读，更多相关《离散题库20套答案.doc（35页珍藏版）》请在金锄头文库上搜索。
1、离散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分，步骤对，结果错，适当扣分，如果求出其一个，另一个
2、直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取范式:(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.
3、（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的子群。或由群的
4、定义来证明。离散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叉树。任何一棵有序树都可
5、以改写为对应的二叉树，方法是：除了最左边的分枝点外，删去所有从每一结点长出的分枝。在同一层次中，兄弟结点间用从左到右的有向边连接。选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上给定结点右邻结点，作为右儿子，以此类推。2（8分）各4分，步骤对，结果错，适当扣分，如果求出其一个，另一个直接写出，也不扣分。只有结果，且结果对，给一半分，只有结果，且结果错，不给分。解：主析取范式:（PQR）（PQR）（PQR）主合取范式:（PQR）（PQR）（PQR）（PQR）（PQR）3.（7分）这是一个求最小生成树的问题，可用多种方法，但必须有思路和过程。解：按该图的生成
6、树建立通讯线路能使城市间直接通讯，按最小生成树建立通讯线路能使城市间直接通讯且总造价最小。（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分
7、），从而,所以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分）
8、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分）
9、四、解答题（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)(P
10、QR)主合取范式:(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:010,y:011,h:10,e:110,n:111.happynewyear的编码信息:100010001000
11、1011111110001010五、证明（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分）证明过程：证法
12、（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
13、=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
