离散数学 练习题.doc

《离散数学 练习题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模拟题一、选择与填空题：1．设是代数系统，其中+和´为普通的加法和乘法，则当A=时，是域。①{x

2、x是整数}②{x

3、x≥0，x是有理数}③{x

4、x≥0，x是实数}④{x

5、x是偶数}⑤{x

6、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上的一个划分，则π所对应的

7、等价关系R应有个有序对。①15②16③17④18⑤14⑥49⑦275．下列代数系统（其中*是普通加法运算），(1)G为整数集合；(2)G为偶数集合；(3)G为有理数集合；(4)G为自然数集合。其中，不是群。6．设G为任意的连通平面图，则有n-m+r=；若G是简单连通平面图(n≥3)，则m≤；若G是简单连通平面图(n≥3)，且G是二部图，则m≤。（其中n表示顶点数，m表示边数，r表示平面数。）7．一棵树T中有2个2度顶点，3个3度顶点，4个4度顶点，且没有大于4度的顶点，那么T中有片树叶。8．设有下列集合，A={0，10，11

8、0，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所示的二部图中，其最大匹配含有条边。5图111．设是格，其中A={1，2，3，4，6，8，12，24>，≤为整除关系，则3的补元是，8的补元是，1的补元是。12．在如图2所示的二叉树中，后序遍历序列为：，中序遍

9、历序列为：。ABCDEFGHJIKLM图213．对于S6中的置换，若表示成不交的轮换之积，则s=，t=，st=。14．设某班有学生50人，其中有28人在第一次考试中得到优，有23人在第二次考试中得到优，有15人两次考试都没有得到优，那么两次考试都得到优的学生人数是。15．设个体域D={a，b，c}，消去下列谓词公式中的量词："x(F(x，y)®$yG(y))Û。二、判断题：1．“你真棒！”是个真命题。（）2．在主合取范式中，每个极大项都对应一个二进制数，该二进制数是极大项的成真赋值。（）3．ÆÍÆ，但ÆÏÆ。（）4．极小元是指集合中大

10、小最小的元素。（）5．{a}Í{{a}，b}（）6．二元关系不是集合。（）57．最大元一定是极大元。（）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的所有

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

12、短路径长度。abcagdefz632734215223564v1v2v4v32．有向图D如图4所示。（1）写出D的邻接矩阵A；（2）D中长度为3的通路有多少条？长度为2的回路有多少条？（3）求该图的可达矩阵，D是哪类连通图？v4v5v3v1v22’．有向图D如图4所示。（1）写出D的邻接矩阵A；（2）D中长度为2的通路有多少条？长度为3的回路有多少条？（3）求该图的可达矩阵，D是哪类连通图？3．用克鲁斯克尔(Kruskal)算法求下列带权无向图的最小生成树，并计算出最小生成树的权值。e1234567891011abcdf4．求命题公式

13、（ØP→Q）Ù（P→R）的主析取范式。5．设七个字母在通讯中出现的频率如下：5a：35%，b：20%，c：15%，d：10%，e：8%，f：6%，g：3%.（1）以频率（或乘100）为权，求最优二元树；（2）求每个字母对