2016年离散深刻复习理解练习知识题

1、(四)一、判断题(每题1分，共10分)1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是惟一的()2. 011 是公式(p q) r的成真赋值3.( xF(x) yG(y)(x F(x)( y G(y)5.三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性。()6. 设 F,R 都是二元关系，则(F R)-1=F-1R-1。()7. 设 n 是任意一个正整数，则一定存在阶是 n 的群.()8. 布尔代数是有界格，也是分配格.()9. 无向完全图Kn(n2 )定是哈密顿图()10. 阶数至少是 2 树的每一条边都是桥，因而它的边连通度是 1.()二、空题(

2、每小题2分，共2 0分)1.谓词公式x(P(x,y)AtQ(t,z) R(x,y,t)中量词 的辖域是2. 设 F(x):x 是人，H(x,y):x 与 y 样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_ 。3.(p q) pq从公式分类角度来看，它为 _式。4. 设 R=,，贝 U R 的对称闭包是 _4.x(F(x) G(x)xF(x) xG(x)5. 设 A,B 是集合，A 3, B 4, A B 2,那么，A B _6. Z6,是模 6 加群，则它的生成元是 _。2 4= _7 整数加群是循环群，其生成元是 _ 和_。8.设A,是偏序集，如果_ 则称A,是(偏序)格。9.一棵

3、二叉树先序遍历得ABDECF，中序遍历得 DBEACF,则后序遍历的结果是(2 )求 A 的极大元和极小元;(3 )求 B=4,6的上确界和下确界。5.求公式(pq) r的主和取范式(化成 MiM2M3的形式)。6 画一棵带权为 2，2，2，3，3，4，5，8 的最优二叉树 T,并计算它的权 W(T)。四、证明题(每小题 6 分，共 18 分)1. 前提：p (q r), q (r s)结论：(p q) s2. 定理(子群判别法 1)设 H 是群G ,?的非空子集，则 H G 当且仅当(1)a, b H , a?b H ;(2)a H , a-1 2 3 H。利用上述定理证明：设 H 是群G

4、,?的非空有限子集。若 H 关于？封闭，则 H 是G 的子群。3. 用数学归纳法证明 n 阶无向树 T 有 n-1 边。(五)一、选择题(每小题2分，共20分。请将答案填在下面的表格内)1从集合分类的角度看，命题公式可分为()A.永真式、矛盾式B.永真式、可满足式、矛盾式C.可满足式、矛盾式D.永真式、可满足式2设 B 不含有 x，x(A(x) B)等值于()A.xA(x) BB.x(A(x) B)C.xA(x) BD.x(A(x) B)3设 S,T,M 是集合，下列结论正确的是()A.如果 SUT=SUM，贝UT=MB .如果 S-T=，贝 U S=T)0D.ST S (T)4、设 R 是集

5、合 A 上的偏序关系，则 R 不一定是（）A.自反的 B.对称的C.反对称的D.传递的5 设 R 为实数集，定义 R 上 4 个二元运算，不满足结合律的是（A.fi(x,y)= x+y设L, 是一个格，则它不满足（）A.1,11,101B.1,001,0011 C. 1,01,001,000 D.0,00,000下图中既是欧拉图又是哈密顿图的是（二、填空题（每题3分，共24分）C. S S SB. f2(x,y)=x_yC. f3(x,y)=xyD. f4(x,y)=maxx,yA.交换律B.结合律C.吸收律 D.消去律设 A=1,2,则群P(A),的单位元和零元是（）A. 与 A B. A

6、与C. 1与 D. 1与 AF 列编码是前缀码的是（).A .KgB.K10C.D .K3,310、下图所示的二叉树中序遍历的结果是A. abcdeB. edcbabdecaD. badceCK2, 3）)01、含 3 个命题变项的命题公式的主合取范式为则它的主析取范式为。（表示成 m m 的形势2、 Z4,模 4 加群，则 3 是_阶元，3 3= _ , 3 的逆元是_。3、 设 V=,其中“ + ” 是普通加法。 x Z，令i(x)=x,2(x)=-x,3(X)=X+5,4(X)=2X，其中有_ 自同构.12 3 4 5 64、 设是集合 A=1，2，3，4,5,6上的一个置换，则把它表2

7、31546示成不相交的轮换的积是 _ 。4、 已知 n 阶无向简单图 G 有 m 条边，则 G 的补图有_ 条边。5、 一个有向图是强连通的充分必要条件是 _ 。7、已知 n 阶无向图 G 中有 m 条边，各顶点的度数均为 3。又已知 2n-3=m ，则 m=8、在下图中从 A 点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是三、计算题(每题9分，共36分)1、 已知命题公式(p q) ( q p)，(1)构造真值表。(2)求主析取范式(要求通过等值演算推出)。2、 R1=, R2=, 求：1(1)R1R2(2)R1(3 )求R2R13、设为一个偏序集，其中，A=1，2，3，4，6，

8、9，12，24,R 是 A 上的整除关系(1 )画 R 出的哈斯图;(2 )求 A 的极大元和极小元；(3 )求 B=4,6的上确界和下确界。4、画一棵带权为 1 , 1, 1 , 3 , 3 , 5 , 8 的最优二叉树 T,并计算它的权 W (T)得分阅卷人四、证明题(共20分)to1、(7 分)前提：p (q s), q, p r结论：r s2、( 7 分)A=(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1),R=v(a,b),(c,d)| (a,b),(c,d) A 且 a+b=c+d .(1)证明：R 是 A 上的等价关系.给出 R 确定的对 A 的

9、划分份类).3、(6 分)设G,是群，S x|x证明 S 是 G的子群.一、选择题(每小题 2 分，共 20 分)1 一个命题公式或一阶逻辑公式的(A .主析取范式B.主合取范式2.下列四个公式正确的是x(A(x) B(x)xA(x) xB(x)x(A(x) B(x) xA(x) xB(x)G 且对于 y G,x y y x,(六)是不惟一的。C.前束范式D .对偶式x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)A.B.C.D.3 设集合 A=a , b , c, d , e，偏序关系 R 的哈斯图下图所示，贝 U 元素的关系不正确的是（）4 .已知 A,B

10、是集合丨 A |=15 ,|B |=10 , | AUB | =20，贝 A AB |=()5 . X=a , b , c, d , e, Y=1 , 2, 3 , 4, f 从 X 到 丫丫 的映射，其中 f(a)=2.f(b)=4,f(c)=1,f(d)=3,f(e)=4, 则 f 是()7 .在下图所示的哈斯图中的偏序集不是格的是（）A. 10B. 5C. 20D . 13A.双射B.满射6 .设 A,B,C 是三个非空集合，则(A. A B A C B CC. A B AC B CC.单射D.不是单射也不是满射）是正确的.B.A BA C B CD. A BA C B CB. a ec

11、8.下图中，（）是欧拉图ABCD9. 关于无向树的描述，不正确的是().A. 无向树是连通图、没有回路，每个边都是桥；B. 无向树是连通图、边数比顶点数少1，任意两个顶点的路径是惟一的;C. 无向树是连通图、没有回路，每个顶点都是割点；D. 无向树是连通图、没有回路，每条边都是割边。10. 关于含有 n 片树叶的最优二叉树描述，不正确的是().A. 含有 n 片树叶的最优二叉树每个分支点都有两个孩子；B. 含有 n 片树叶的最优二叉树分支点的个数是 n-1 ;C. W(T)等于个分支点的权重(构造最优二叉树时产生)之和；D. 在权重一定的前提下，含有 n 片树叶的最优二叉树是惟一的。二、计算题

12、(每小题 10 分，共 40 分)1.(1)求(p q) r) p的主析取范式；(2)根据主析取范式直接写出主合取范式；(3)根据主析取范式直接写出真值表。2. 设集合 A=a , b , c, d, A 上的关系 R=,vb,a,vc,d,vd,c求:(1)画出 R 的关系图；(2)求出 R 的传递闭包 tr(R);(3) tr(R)中再添加一些元素后得 D(R),若使 D(R)是等价关系，则 tr(R)中再添哪些元素后得 D(R)?3. (1)下图的最下生成树；(2) 求该图的点连通度和边连通度；(3) 求 A 到 B 的最短路径的长度。4.(10 分)对于下有向图,(1)写出度序列和出度

13、序列;(2)写出邻接矩阵 A,第一行元素之和的含义是什么?求 A4，据此说明从 A 到 A 的长度为 4 的回路用多少?、证明题x, yu,vR当且仅当 xv yu，证明：R 为等价关系设 A 是正整数集合，在 A A 上定义二元关系 R 如下:2. 设 R 为实数集，+为普通加法，？为普通乘法，R , *是一个代数系统，*是 R 上 的一个二元运算，使得x,y R，都有x*y=x+y+x ?证明:R，*是含幺独异点。3. 设 fi，f2都是一从代数系统A，*到代数系统B，的同态。设 g 是从 A 到 B的一个映射，使得对任意 a A，都有 g(a)=fi(a) f2(a)；证明：如果B，为一个可交换半群，那么 g 是一个由A，*到B， 的同态映射。10. r=5,当 s=_ 时，完全二部图 匚&才可能存在完美匹配三、计算题(1-4 题每题 8 分；5-6 题每题 10 分，共 52 分)1.Ri=v1,2,v2,1,v2,3,R2=,求：Rj (2) R1R2R2* 1 2 3(4)t(R1)(传递闭包)10 1 0 0 1 0 12 设 G=a. , c ,c,d ,M，G 上的运算是