《(信息与计算)离散复习题》由会员分享，可在线阅读，更多相关《(信息与计算)离散复习题（5页珍藏版）》请在金锄头文库上搜索。
1、离散数学复习题1、设 ，写出 R 的关系矩阵，且画出2,4,3,24,1.4,32 RA其关系图。2、设 A=a，b，c，则 A 的幂集 p(A)=3、 ，则 R 的自反闭包是，对称2,43,14,.4,1 闭包是，传递闭包是。4、合式公式 的主析取和主合取范式是 QP5、判断下列命题是否正确（1） ，,AaAa（2）一个二元关系如果是对称的，则一定不会反对称。（3）零图是二分图。（4）欧拉图一定是哈密顿图。（5）在 中不存在完美匹配。3,5k6、填空：（1） 、任何一棵树的顶点数与边数之间的关系为（2）下列哪些为命题的是。1、 今天真冷啊！2、 他穿着红色外衣，打着伞。3、 很好！4、 因为
2、人都是要死的，所以苏格拉底是要死的。5、 X-506、 明年 5 月 1 日是晴天。（3）有割边的图的边连通度是。（4）有割边的图的边连通度是。（5）下面为前缀码的是A=01，00，11； B=10， 110，101 ；7、将 的约束变元改名后为。()()xPQx8、在一阶逻辑中将命题符号化(1) 所有火鸟都会飞。 (2) 有些人喜欢吃零食。（3）所有火车比所有汽车跑得快。（4）没有鸟不吃食。9、 若 A、B 、C 为三个集合，说明 一定成立吗? ，若不对，举CBA,例说明。 10、 2,4,3,24,1.4,321 RA说明 R 是否自反，反自反？对称？反对称？传递的？ 11、 判断哪些是欧
3、拉图，哪些是哈密顿图，哪些是偶图（二分图） 。12、 ，问 A 上的空关系 满足否自反，反自反？对称？反对称？传递的？4,321A13、求公式 的主析取范式和主合取范式。qp14、求出谓词公式 的前束范式. 中哪些是自由)(),(xQyxP)(),(xQyxP变元.15、 的前束范式是()()x16、 ，求出公式1:,apbD 1:).(0:),(0:),( bpab在以上解释 下的真值,(要过程).)(yxI17、证明：整数 Z 对于乘法运算作成半群，且找出单位元和零元。18、设 ， ，求1,4,2,3.4,321RA 1,42,S.SR19、 ，,(,.,（1）写出 R 的关系矩阵（2）求
4、 R 的自反闭包，对称闭包，传递闭包（用矩阵求） 。20、整数 Z 对于加法运算作成群。21、构造下列公式的真值表,并据此判断它是重言式、矛盾式或可满足式。)(qp； 22、求 PQ 的主析取和主合取范式。23、求下面公式的前束范式 );()(xGxF24、设 ， ，求 ， ，3,22,63,1FGF25、求合式公式 的主析取和主合取范式。 P26、设 A1,2,3 ， ， R1，R 2，R 3 是 A 上的关系，其中AR1, R2, R3 ，R4,，,则自反的关系有，对称的关系有，传递的关系有。传递关系有27、 的边数为3,5k28、13 条边，一个 2 度点，其余都是 3 度点的图，顶点数
5、是29、5 个顶点的含边数最多的简单图是30、含 n 个顶点的简单图中，每个顶点的度数只可能是。31、画出 8 个顶点的正则二叉树。32、判断哪些运算是自然数集的二元运算：（1） xy= x+y+4；（2）xy= x+y-4（3）xy= x（4）xy= （ x，y）（5） min,33、画出一个完全正则二叉树，使得有 8 片叶。画一个 7 个顶点的欧拉图，使它同时是哈密顿图。画一个哈密顿图但不是欧拉图， 。34、分别判断序列（3，2，1，4） ， （5，3，2，4，2）是否为度序列？计算题：35、求一个图的补图，如1v2ve36、A=1，2，3，4，5，7，8，12，24 ，R 是整除关系，画
6、出 R 的哈斯图，判断子集2 ， 3，4 是否有最大最小元，极大极小元，上下确界，若有，请求出来。37、对无向(有向) 图,写出相邻矩阵,关联矩阵.如38 对于一个边赋权图, 求最短路径.39对于一个有向赋权图,求最大网络流.40 对于一个无向连通图,求最小生成树,且写出权.如v1v2v3v4v5v61112223 357641、求图的点连通度和边连通度，如 52,k42画出 5 个顶点的所有非同构的树。43证明：在任何 n 阶非平凡的无向树 T 中至少有两片树叶。44求带权 1,2,2.5,2.6,2.7,5,6,7 的最优二叉树 T。45：证明：在整数集 Z 中,定义 ,证明 Z 关于给定的运算作成群.6xy
