《离散复习题资料》由会员分享，可在线阅读，更多相关《离散复习题资料（12页珍藏版）》请在金锄头文库上搜索。
1、1, 使用Dijkstra法，求出下图顶点A到其余顶点的最短路径。（在表格中体现该算法的求解步骤）。tABCDEF1(0,)*(+, )(+, )(+, )(+, )(+, )2(6,A)(3,A)*(+, )(+, )(+, )3(5,C)*(6,C)(9, C)(+, )4(6,C)*(9,C)(14,D)5(7,D)*(14,D)6(12,E)*2、一个n(n=2)阶无向简单图G中，r为奇数，已知G中有r个奇数顶点，请证明中有r个奇度数顶点解：由G得补图定义可知，G为 由于n为奇数，所以中各顶点的度数n-1为偶数对于图G的任意结点v应有v也是G的顶点deg(v)+deg(v)=n-1(第
2、一个deg(v)代表的是图G，第二个代表n-1为偶数，所以G中有r个奇数度节点同理在G中偶数度顶点在中仍为偶数度顶点则中也有r个奇度数顶点3、已知A=3，4，B=1，2,3求A到B的所有函数。并指出入射函数。解： F1=, F2=, F3=, F4=,F5=, F6=, F7=, F8=,F9=,函数性质：1，满射，无。2，单射，f2,f3,f4,f6,f7,f84、已知G有21条边，4个3度顶点，其余顶点度数至少为5，求G图最多几个顶点？解：由题目可知共有21*2=42个度剩余度数为42-3*4=30305=6所以最多6+4=10个顶点5、设A=a,b,c,求p（A）*A解：= ,a,b,c
3、,a,b,a,c,b,c,a,b,c所以= , 6、求1至200之间不能被2,3,5整除的元素个数。解：设能被2，3，5整除的数字集合为A,B,CA=200/2=100B=200/3=66C=200/5=40AB=200/6=33AC=200/10=20BC=200/15=13ABC=200/30=6ABC=100+66+40-33-20-13+6=146所以不能被2，3，5整除的个数为200-146=547、已知S=,R为A上关系，则此关系共有多少种？如果R1,R2为R上关系，且分别为R1=,R2=,分别求出r(R1)，S(R1)， R1R2, R2R1， t(R1)，解： =512种r(R
4、1)=R1=, , = ,S(R1)=R1 =, ,=,R1R2=,R2R1=,t(R1)=R1 因为=,=,所以t(R1)= ,8、x(F(x)yG(x,y,z)zH(x,y,z)解： xy(F(x)G(x,y,z) zH(x,y,z)xy(F(x)G(x,y,z) zH(x,y,z)xyz(F(x)G(x,y,z) H(x,y,z)9、设个体域D=2,3,则请消去公式 中的量词.xyF(y,x)x(F(2,x)F(3,x)(F(2,2) F(3,2) (F(2,3) F(3,3)10、求下列各式的主析取范式，主合取范式(pq) r解：主析取范式：(pq) r(pq) r(pq) (rr)
5、(r(pp)(pqr) (pqr) (pqr) (pqr) (pqr) 所以主合取范式： 11、求出下图的邻接矩阵,求出 到 长度小于3的所有通路个数解： 邻接矩阵为A(D)=， 所以通路个数为1+2=312、构造下面推理的证明前提： 结论：证明：p p T p T T13、设A=2，3，4，5，6，8，9，如果R是A上的模5同余关系，请写出R及A中每个元素的等价类。21、 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全是树叶. 试求树叶数, 并画出满足要求的非同构的无向树. 解 用树的性质m=n-1和握手定理. 设有x片树叶，于是 n=1+2+x=3+x, 2m=2(2+x)
6、=13+22+x解得x=3，故T有3片树叶.22、已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构的无向树. 解 设T的阶数为n, 则边数为n-1, 4度顶点的个数为n-7. 由握手定理得 2m=2(n-1)=51+21+31+4(n-7)解得n=8, 4度顶点为1个. 1 设集合A=2,a,3,4，B = a,3,4,1，E为全集，则下列命题正确的是( )。(A)2A (B)aA (C)aBE (D)a,1,3,4B.2 设集合A=1,2,3,A上的关系R(1,1),(2,2),(2,3),(3,2),(3,3)，则R不具备
7、( ).(A)自反性(B)传递性(C)对称性(D)反对称性3 设半序集(A,)关系的哈斯图如下所示，若A的子集B = 2,3,4,5,则元素6为B的( )。(A)下界 (B)上界(C)最小上界 (D)以上答案都不对4 下列语句中，( )是命题。(A)请把门关上 (B)地球外的星球上也有人 (C)x + 5 6 (D)下午有会吗？5 设I是如下一个解释：Da,b, 则在解释I下取真值为1的公式是( ).(A)$xyP(x,y) (B)xyP(x,y) (C)xP(x,x) (D)x$yP(x,y).6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ).(A)(1,2,2,3
8、,4,5) (B)(1,2,3,4,5,5) (C)(1,1,1,2,3) (D)(2,3,3,4,5,6).7. 设G、H是一阶逻辑公式，P是一个谓词，G$xP(x), HxP(x),则一阶逻辑公式GH是( ).(A)恒真的 (B)恒假的 (C)可满足的 (D)前束范式.8 设命题公式G(PQ)，HP(QP)，则G与H的关系是( )。(A)GH (B)HG (C)GH (D)以上都不是.9 设A, B为集合，当( )时ABB.(A)AB(B)AB(C)BA(D)AB.10 设集合A = 1,2,3,4, A上的关系R(1,1),(2,3),(2,4),(3,4), 则R具有( )。(A)自反
9、性 (B)传递性(C)对称性 (D)以上答案都不对11 下列关于集合的表示中正确的为( )。(A)aa,b,c (B)aa,b,c(C)a,b,c (D)a,ba,b,c12 命题xG(x)取真值1的充分必要条件是( ).(A) 对任意x，G(x)都取真值1. (B)有一个x0，使G(x0)取真值1. (C)有某些x，使G(x0)取真值1. (D)以上答案都不对.13. 设G是连通平面图，有5个顶点，6个面，则G的边数是( ).(A) 9条 (B) 5条 (C) 6条 (D) 11条.14. 设G是5个顶点的完全图，则从G中删去( )条边可以得到树.(A)6 (B)5 (C)10 (D)4.1
10、5. 设图G的相邻矩阵为，则G的顶点数与边数分别为( ).(A)4, 5 (B)5, 6 (C)4, 10 (D)5, 8.16. 与命题公式等价的公式是（ ）（A） （B） （C） （D）17. 设集合,A上的二元关系不具备关系( )性质（A） (A)传递性 (B)反对称性 (C)对称性 (D)自反性18. 在图中,结点总度数与边数的关系是( )(A) (B) (C)(D) 19. 设D是有n个结点的有向完全图,则图D的边数为( )(A) (B) (C) (D)20. 无向图G是欧拉图,当且仅当( )(A) G的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数（C）G连通且所有结点的
11、度数都是偶数 (D) G连通且G的所有结点度数都是奇数。1. C. 2. D. 3. B. 4. B.5. D. 6. C. 7. C.8. A. 9. D. 10. B. 11. B. 13. A. 14. A.15. D16 B 17 D 18 C 19 A 20 C1. 计算机系期末要安排7门公共课的考试，课程编号为1到7。下列每一对课程有学生同时选修：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，6和7。这7门课的考试至少要安排在几个不同的时间段？给出一个安排方案。2解：由题意可设G=,其中V有7个结点分别表示7门公共课考试的课程编号，若Vi,Vj，且Vi,Vj表示有学生同时选修每一对课程，则，由此可画图G为：137
