离散数学 练习题

1、模拟题一、选择与填空题：1设是代数系统，其中+和为普通的加法和乘法，则当A= 时，是域。x|x是整数x|x0，x是有理数x|x0，x是实数x|x是偶数x|x=a+b，a, b是有理数2设G是由6个元素构成的循环群，a是G的一个生成元素，则G有_个子群，G的生成元是_。3 = ，- = 。4设集合A=a，b，c，d，e，f，g，=a，b，c，d，e，f，g是A上的一个划分，则所对应的等价关系R应有 个有序对。151617181449275下列代数系统（其中*是普通加法运算），(1) G为整数集合；(2) G为偶数集合；(3) G为有理数集合；(4) G为自然数集合。其中， 不是群。6设G为任意的

2、连通平面图，则有n-m+r = ；若G是简单连通平面图(n3)，则m ；若G是简单连通平面图(n3)，且G是二部图，则m 。（其中n表示顶点数，m表示边数，r表示平面数。）7一棵树T中有2个2度顶点，3个3度顶点，4个4度顶点，且没有大于4度的顶点，那么T中有 片树叶。8设有下列集合，A =0，10，110，1111，B =1，01，001，000，C =1，11，101，001，0011，D =b，c，aa，ac，aba，abb，abc，则 是前缀码。9设集合A=a，b，c，R=，则R是 。自反的反自反的对称的反对称的传递的不可传递的10在图1所示的二部图中，其最大匹配含有 条边。图111设

3、是格，其中A=1，2，3，4，6，8，12，24，为整除关系，则3的补元是 ，8的补元是 ，1的补元是 。12在如图2所示的二叉树中，后序遍历序列为： ，中序遍历序列为： 。ABCDEFGHJIKLM图213对于S6中的置换，若表示成不交的轮换之积，则s = ，t = ，st = 。14设某班有学生50人，其中有28人在第一次考试中得到优，有23人在第二次考试中得到优，有15人两次考试都没有得到优，那么两次考试都得到优的学生人数是 。15设个体域D =a，b，c，消去下列谓词公式中的量词：x(F(x，y)$yG(y) 。二、判断题：1“你真棒！”是个真命题。（ ）2在主合取范式中，每个极大项都

4、对应一个二进制数，该二进制数是极大项的成真赋值。（ ）3，但。（ ）4极小元是指集合中大小最小的元素。（ ）5aa，b（ ）6二元关系不是集合。（ ）7最大元一定是极大元。（ ）8函数的逆也是一个函数。（ ）9设S，T为任意集合，若S-T=，则S=T。（ ）10由握手定理可以推导出无向图中的奇度顶点有奇数个。（ ）三、综合题：1设是偏序集，A =1，2，3，4，6，8，12，24，60，R是A上的整除关系，（1）画出R的哈斯图；（2）设子集B =2，4，6，12，写出B的极大元、极小元、最大元、最小元、上界、下界、最小上界和最大下界。1设偏序集，其中，S30表示30的所有因子集合，D表示整除关

5、系。（1）试作出该偏序集的哈斯图；（2）设B=1,3,6,15，求B的最大元素、最小元素、极大元素、极小元素、最小上界和最大下界。 2在一阶逻辑中将下列命题符号化：（1）没有不吃饭的人。（2）在北京卖菜的人不全是东北人。（3）自然数全是整数。（4）有的人天天锻炼身体。2在一阶逻辑中将下列命题符号化：（1）所有大学生都要参加考试。（2）有些大学生爱唱歌。（3）并非每个实数是无理数。（4）虽然有些实数是无理数，但未必一切实数都是无理数。四、计算题： 1用Dijkstra算法求图3中a到z的最短路径，并求出最短路径长度。abcagdefz632734215223564v1v2v4v32有向图D如图4

6、所示。（1）写出D的邻接矩阵A；（2）D中长度为3的通路有多少条？ 长度为2的回路有多少条？（3）求该图的可达矩阵，D是哪类连通图？v4v5v3v1v22有向图D如图4所示。（1）写出D的邻接矩阵A；（2）D中长度为2的通路有多少条？ 长度为3的回路有多少条？（3）求该图的可达矩阵，D是哪类连通图？3用克鲁斯克尔(Kruskal)算法求下列带权无向图的最小生成树，并计算出最小生成树的权值。e1234567891011abcdf4求命题公式（PQ）（PR）的主析取范式。5设七个字母在通讯中出现的频率如下： a：35%，b：20%，c：15%，d：10%，e：8%，f：6%，g：3%.（1）以频率（或乘100）为权，求最优二元树；（2）求每个字母对应的前缀码；（3）传输10 000个按上述比例出现的字母需要传输多少个二进制位？比用长度为3的等长码子传输节省了多少个二进制位？5设七个数字在通讯中出现的频率如下： 0：35%，1：20%，2：15%，3：10%，4：8%，5：6%，6：6%.（1）以频率（或乘100）为权，求最优二元树；（2）求每个数字对应的前缀码。五、证明题：1证明下列命题中结论的有效性：如果这里有球赛，则通行是困难的。如果他们按时到达，则通行是不困难的。他们按时到达了。所以，这里没有球赛。1构造下面推理的证明：如