《2022年2022年离散数学试题库 .pdf》由会员分享,可在线阅读,更多相关《2022年2022年离散数学试题库 .pdf(22页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 模拟试题(一)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1给定命题公式如下:)()(pqqp成真赋值的个数为()。A1 2 3 4 2.设个体域 D=a,b,公式xxSxxP在 A 中消去量词后应为()AxSxPB)()(bSaSbPaPCbSaPD)()(bSaSbPaP3若 R 和 S是集合 A 上的两个关系,则下述结论正确的是()。A若 R和 S是自反的,则R S也是自反的 B若 R和 S是对称的,则R S也是对称的 C若 R和 S是反对称的,则R S也是反对成的 D若 R和 S是传递的,则R S也是传递的4设全集U=1,2,3,.
2、,20,A,B,C是其子集,其4|xxA,100|,076|22xxCxxxB则CBA()。A16,17,18,19,20 B1,2,3,4,5 C10,11,12,13,14,15 D 1,2,3,4,5,6,7 5下面偏序集构成有界格的是()。A 6全体自然数所组成的集合的最小元为()。A负数最小的正数 0 1 7对任何 a A,形成的 A 上的等价关系R 的等价类 aR为()。A空集非空集空集也可以为非空集 xxA 8设S=Q Q,其中Q 为有理数集合,定义S 上的二元运算“*”,,S,有bbyaxyxba,*,,则 是()。A可交换的可结合的既是可交换的,又是可结合的不是可交换的,也不
3、是可结合的9.设有向图 D=的邻接矩阵为0100100001000121)(DA,则D中 v1到 v3长度为 4 的通路有()条。A4 6 8 9 10.下面那种描述的图不一定是树()。A无回路的连通图有 n 个顶点的n-1 条边每对顶点都有通路的图连通但删去一条边则不连通的图11.一颗二叉树后序遍历的结果是bdeca,中序遍历的结果是badce,则根结点的右子树有()结点。A1 B2 C3 D4 12.设函数 f:NN(N 为自然数集),f(n)=n+1,下面四个命题为真的是()A.f是单射 B.f是满射 C.f是双射的 D.f非单射非满射13.设 S=0,1,则 S满足()。A.在普通乘法
4、下封闭,在普通加法下不封闭 B.在普通加法和乘法下都封闭C在普通加法下封闭,在普通乘法下不封闭 D在普通加法和乘法下都不封闭名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 22 页 -2 14.下图中()是欧拉图。A B C D 15.设集合 A=a,b,c,d,e,偏序关系 R的哈斯图如左图所示,则元素的关系不正确的是()。Adc Bea C ba D ed二、填空题16.设无向图 G有 12 条边,有 6 个 3 度顶点,其余顶点度数均小于3,则 G种至少有顶点。17.在彼得森图中至少添加条边才能构成欧拉图。18.由 Huffman 算法,带权1,3,4,5,6 的最优二叉树
5、的权W(T)=。19.设 V=为代数系统,其中A=0,1,2,3,4。a,bA,a*b=(ab)mod5。关于运算“*”的幺元是。20设 Z 为整数集,a,bZ,有 a b=a+b-1,则 a 的逆元=。21集合 a,b,c,d上关系 R的关系图如左所示,则R的传递闭包(用集合表示)为。22.设 R是由方程 x+3y=12 定义的正整数集N 上的关系,即123,|,yxNyxyx,则 6,4,3,2R,3 在 R下的象是。23.若集合 A的基数|A|=10,则其幂集|P(A)|=。三、计算题24判断正整数集合Z+和下面的二元运算是否构成代数系统。如果是,则说明这个运算是否满足交换律、结合律和幂
6、等律,并求出单位元和零元。(1)a*b=min(a,b)(2)ab=(a/b)+(b/a)25.用主析取范式判断rqp与rpq是否等值。26.设,为上关系,关系矩阵为,(1)画出关系图。(2)求,。(3)求,。(4)指出具有的性质。(5)是偏序关系吗?能否画出哈斯图?abcdefg名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 22 页 -3 27求下图的最小生成树,写出过程,并计算权。四、证明题28在命题逻辑中构造下面推理的证明。前提:ps,qr,r,p q结论:s 29设无向图G 是由 k(k2)棵树组成的森林,已知G 中有 n 个结点,m 条边,证明m=n-k。30证明对于
7、任意集合A,B,C,有(A-B)-C=(A-C)-(B-C)五、应用题3175 名儿童到公园游乐场,他们在那儿可以骑旋转木马,坐滑行铁道,乘宇宙飞船,已知其中20 人这三种东西都乘过,其中 55 人至少乘过其中的两种。若每样乘坐一次的而费用是0.50 元,公园游乐场总共收入70 元,试确定有多少儿童没有乘过其中任何一种。32有四个村庄的地下各有一个防空洞甲、乙、丙、丁,相邻两个防空洞之间有地道相通,且每个防空洞各有一条地道与地面相通,如下图所示(图中表示地道)。问能否从某一个防空洞开始,每个地道走一次且仅走一次后回到该防空洞。(要求有一定的分析过程)模拟试题(二)三、单项选择题在下列每小题的四
8、个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1下列是两个命题变元p,q 的小项是()A pp q Bp q Cp q Dp p q 2令 p:今天下雪了,q:路滑,则命题“虽然今天下雪了,但是路不滑”可符号化为()A pq B pq Cp q Dpq 3下列语句中是命题的只有()A 1+1=10 Bx+y=10 C sinx+siny0 D x mod 3=2 4下列等值式不正确的是()A(x)A(x)(x)A(x)B(x)(B A(x)B(x)A(x)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 22 页 -4 C(x)(A(x)B(x)(x)A(x)(x
9、)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5谓词公式xP(x,y)t(Q(t,z)x yR(x,y,t)中量词t 的辖域是()A t(Q(t,z)x yR(x,y,t)BQ(t,z)x yR(x,y,t)Cx yR(x,y,t)DQ(t,z)6设 R 为实数集,函数f:RR,f(x)=2x,则 f 是()A满射函数 B入射函数C双射函数 D非入射非满射7设 A=a,b,c,d,A 上的等价关系R=,IA,则对应于R 的 A 的划分是()A a,b,c,d B a,b,c,d C a,b,c,d Da,b,c,d 8设 A=?,B=P(P(A),以下正确的式子是()A
10、?,?B B?,?B C?,?B D?,?B 9设 X,Y,Z 是集合,“-”是集合相对补运算,下列等式不正确的是()A(X-Y)-Z=X-(Y Z)B(X-Y)-Z=(X-Z)-Y C(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)10设*是集合 A 上的二元运算,称z 是 A 上关于运算*的零元,若()A z A,且有 x*z=z*x=z Bz A,且有 x*z=z*x=x C z A,且有 x*z=z*x=z DzA,且有 x*z=z*x=x 11在正整数Z+上,下列定义的运算中不可结合的只有()A a*b=min(a,b)Ba*b=a+b C a*b=GCD(a,b
11、)(a,b 的最大公约数)Da*b=a(mod b)12设 R 为实数集,R+=x|x Rx0,*是数的乘法运算,是一个群,则下列集合关于数的乘法运算构成该群的子群的是()A R+中的有理数 BR+中的无理数 C R+中的自然数 D1,2,3 13设 是环,则下列正确的是()A 是交换群B 是加法群C 对*是可分配的D*对 是可分配的14图 1 所示的 6 个图中,强连通图为()。A.(1)(2)(3)B.(4)(5)(6)C.(1)(3)(4)(6)D.(1)(5)(6)15设 G 是连通平面图,G 中有 6 个顶点 8 条边,则 G 的面的数目是()A2 个面 B3 个面C4 个面 D5
12、个面二、填空题16 前束范式具有形式(Q1V1)(Q2V2),(QnVn)A,其中 Qi(1 i n)为,A为的谓词公式。17某集合 A上的二元关系R具有对称性,反对称性,自反性和传递性,此关系R是。18设 Z 是整数集,在Z上定义二元运算*为 a*b=a+b+ab,其中+和是数的加法和乘法,则代数系统 的幺元是,零元是。19图 2 所示平面图有3 个面 R0,R1和 R2,其中 deg(R0)=。20图 3 中,结点 v2的度数是。图 2 图 3 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 22 页 -5 21.设 R为 A上的关系,则R的自反闭包为,对称闭包为。22.公式
13、)()(qpqp的主析取范式为。三、计算题23求出从 A=1,2 到 B=x,y 的所有函数,并指出哪些是双射函数,哪些是满射函数。24判断下面集合对于给定运算能否构成群,并简要说明理由。(1)实数集合R 关于运算,其中ab=2(a+b)(2)非零实数集合R*关于运算,其中ab=2ab25画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。26在偏序集 中,其中 Z=1,2,3,4,6,8,12,24,是 Z 中的整除关系,画出其哈斯图,并求集合 D=2,3,4,6 的极大元,极小元,最大元,最小元,上界,下界,最小上界和最大下界。27求图 4 所示平面图G的对偶图,并判断G是否为
14、自对偶图。四、证明题28证明qprssprqqp图 4 29证明在无向图中顶点的连通关系是等价关系。五、应用题30对 100 名工作人员的调查结果表明,有32 人学过日语,20 人学过法语,45 人学过英语。其中15 人既学过日语又学过英语,7 人既学过日语又学过法语,10 人既学过法语又学过英语,30 人没有学过这 3 门语言中的任何一种。求至少学习过以上3 种语言中两种语言的人数。31设有 a,b,c,d,e,f,g 等七个人,已知a会讲英语;b 会讲英语、汉语;c 会讲英、俄语;d 会讲日、汉语;e 会讲德语、俄语;f 会讲法语、日语;g 会讲法语、德语。试用图论方法安排园桌座位,使每人
15、都能与其身边的人交谈。模拟试题(三)四、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1一个公式在等价意义下,下面那个写法是唯一的()。A析取范式B合取范式C主析取范式D以上答案都不对2令 p:今天下雨了,q:我上学,则命题“因为今天下雨了,所以我不上学了”可符号化为()Apq Bpq Cp q Dpq 3谓词公式x(P(x,y)xQ(x,z)R(x,y,z)中量词的辖域是()AQ(x,z)R(x,y,z)BR(x,y,z)CQ(x,z)D P(x,y)xQ(x,z)R(x,y,z)4设 R 为实数集,函数f:RR,f(x)=xe,则 f 是()A满
16、射函数B单射函数C双射函数D非单射非满射5设 A=a,b,c,d,A 上的等价关系R=,IA,则对应于R 的 A 的划分是()Aa,b,c,d Ba,b,c,d Ca,b,c,d Da,b,c,d 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 22 页 -6 6设 A=?,B=P(A),以下正确的式子是()A?,?A B?,?A C?,?B D?,?B 7设,G是群,Gba,则下列结论不正确的是()A111)(ababBbax有惟一解Cyxayax,则Dbaab8在自然数集N 上,下列定义的运算中不满足结合律的()Aa*b=min(a,b)Ba*b=a+b Ca*b=gcd(a
17、,b)(a,b 的最大公约数)Da*b=a-b 9不同构的有2条边的 4 阶无向简单图的个数为()A1 B2 C3 D 4 104 阶无向连通图G 是欧拉图,则它的度序列可能是()A 1,2,3,4 B2,4,6,8 C1,2,4,6 D5,2,3,4 11下列命题中,。A海水是咸的当且仅当雪是白的B如果成都是直辖市,那么北京是中国的首都C若太阳从西边落下,则2 是奇数D夏天冷当且仅当冬天热12设 R是集合 A1,2,3,4上的二元关系,R,则 R不具有下面那种性质。A自反性B反自反性 C反对称性 D 传递性13.下面图中,()是平面图.ABCD14 A1 B2 C 3 D4 15设简单图G
18、所有结点的度之和为12,则 G 一定有()。A3 条边B4 条边C5 条边D6 条边二、填空题16量词否定等值式)(xxA _。17.关于命题变项p,q,r的命题公式的主析取范式是76531mmmmm,则主合取范式是(用公式表示)_ .18.设 R=,,则 dom(R)=。19.设 G是连通的 n 阶 m条边 r 个面的可平面图,则反映结点数、边数、面数之间关系的欧拉公式是_。20.无向图 G=,V=a,b,c,d,E=e1,e2,e3,e4,其中 e1=(a,a),e2=(a,d),e3=(a,c),e4=(b,c),则它的关联矩阵为:21设S(x)x 是大学生;K(x)x 是运动员。则命题
19、:“有些运动员不是大学生”的符号化为。22设54321,A,AAR,224321,R求)(Rr=,)(Rs=23设 G 是完全二叉树,G 有 15 个点,其中8 个叶点,则G 的总度数为 _,分枝点数为_。三、计算题24 A=a,b,c,R1=,R2=,求:(1)R1-1 (2)名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页,共 22 页 -7 12RR(3)R1在 A上的限制25.已知图 G有 10 条边,4 个 3 度结点,其余结点的度数均小于等于2,问该图至少有几个结点?为什么?26.下图是偏序集 的哈斯图,求abcdefgh27.命题公式 F 含有 3 个命题变项p,q,r,
20、其所有成真赋值为:000,001,110,111,求:(1)画出真值表;(2)写出主析取范式;(3)指出公式的类型28求下图的最小生成树,写出过程,并计算权。abcdefh12345567866四、证明题29证明对于具有k(k2)个连通分支的平面图G,有 n-m+r=k+1。其中 n,m,r 分别为 G 的顶点数,边数和面数。30设 A=1,2,3,4,关系)AA()AA(R,Ad,c,b,a|,R,cbdadcba,证明:R是等价关系五、应用题31下述逻辑推理是否有效?证明你的结论。所有羊都吃草,所有死羊都不吃草。所以,所有死羊都不是羊。32已知英文字符串adacatedecade,试用二进
21、制字符串代替此英文字符串,并保证该英文字符串与二进制串构成一一对应。模拟试题(四)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1设命题公式G=(pq),H=p(q p),则 G与 H的关系是()A.GH B.HG C.可满足 D.以上都不是2设集合 A=1,2,3,10,关于集合A 为不封闭的运算是()。A.x*y=maxx,y B.x*y=minx,y C.x*y=x 与 y 的最大公约数 D.x*y=x 与 y 的最小公倍数3设论域 E=a,b,且 P(a,a)=T,P(a,b)=F,P(b,a)=T,P(b,b)=F 则在下列公式中真值为
22、T的是()A.xyP(x,y)B.xyP(x,y)C.xP(x,x)D.x yP(x,y)4设 A=a,a,下列式子中正确的有()。A.aP(A)B.aP(A)C.aP(A)D.以上都不是5设 R,S 是集合 X=1,2,3,4 上的两个关系,其中R=,S=,。则 S是 R的()闭包。A.自反 B.对称 C.传递 D.以上都不是6设 S=1,1/2,2,1/3,3,1/4,4,“*”为普通乘法,则 是()。A.半群,但不是独异点 B.是独异点,但不是群 C.群 D.不是代数系统7设集合 A=a,b,A上的关系 R=,,则 R是()(1)写出集合A,R;(2)求 A的极大元和极小元;(3)求 B
23、=e,f的上确界和下确界。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页,共 22 页 -8 A.是等价关系但不是偏序关系 B.是偏序关系但不是等价关系C.既是等价关系又是偏序关系 D.既不是等价关系又不是偏序关系8G是连通的平面图,有5 个结点,6 个面,则 G的边数为()A.6 B.5 C.11 D.9 9下面命题中,为真的是()。A.完全图 Kn(n1)都是欧拉图 B.完全二部图Kn,m(n1,n 1)都是欧拉图 C.完全图 Kn(n3)都是哈密顿图 D.完全二部图Kn,m(n1,n 1)都是哈密顿图10设集合 A=a,b,c,d,B=1,2,3,4,则从 A到 B的函数 f=
24、,是()。A.f是双射函数 B.f是入射函数C.f是满射函数 D.f即不是满射又是不是入射函数11设,G是群,Gba,则下列结论不正确的是()A111)(ababBbax有惟一解Cyxayax,则Dbaab12在自然数集N 上,下列定义的运算中不满足结合律的()Aa*b=min(a,b)Ba*b=a+b Ca*b=gcd(a,b)(a,b 的最大公约数)Da*b=a-b 13 在简单无向图G=(V,E)中,如果 V 中的每个结点都与其余的所有结点邻接,则该图称为()。A连通图B强连通图C完全图D 平凡图。14对一阶逻辑公式(,)(,)(,)xy P x yQ y zxP x y的说法正确的是(
25、).A x 是约束的,y 是约束的,z是自由的;Bx 是约束的,y 既是约束的又是自由的,z 是自由的;C x 是约束的,y 既是约束的又是自由的,z 是约束的;D x 是约束的,y 是约束的,z是约束的.15.下面图中,()是平面图.ABCD二、填空题16已知集合A=,1,2,则 A的幂集为 _。17已知命题公式G=(p q)r,则 G的主合取范式是_ _。18在有理数集合Q 上定义二元运算“*”,x,yQ 有 x*y=x+y-xy,则当xQ,当 x-1 时,其逆元为。19设集合 A=a,b,c,d,A 上关系 R=,则关系 RoR-1=_。20设 A=0,2,3,4,5,8,B=10,12
26、,13,14,15,16,则 A到 B的一个双射函数为_。21无孤立结点的有限有向图是欧拉图的充要条件是_ _。22具有 16 个结点的完全有向图其边数一定为_。23设 a 是群 的幂等元,则a一定是。24设 G 是完全正则二叉树,G 有 15 个点,其中8 个叶点,则G 的总度数为 _,分枝点数为 _。三、计算题25设集合 A=1,2,3,试写出 A 上的所有等价关系。26.是否可以分别画出一个图,使各点的度与下面给出的序列一致。如可能,画出符合条件的图,如不可能,说明原因。(1)3,3,3,3,3,3(2)3,4,7,7,7,7(3)1,2,3,4,5,5 27.设 T 是如下的二叉树,写
27、出对T 进行先序遍历、中序遍历和后序遍历时访问节点的顺序。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页,共 22 页 -9 28.设 R 是实数集,At=x|xR Ktxt+1,其中 K0=K2=0,K1=K3=-1,K4=-2,令 S=At|t=0,1,2,3,4。画出偏序集 的哈斯图,并求它的极大元、极小元、最大元和最小元。说明该偏序集构成什么格?29给定解释如下:(1)3,2D(2)2a(3)2)3(,3)2(ff(4)1)3(,0)2(:)(FFxF3,2,1),(:),(jijiGyxG1)3,3()2,2(:),(LLyxL0)2,3()3,2(LL求下列各式的值,并说
28、明理由:(1)),()(axGxFx(2))(,()(xfxGxfFx(3)),(yxyLx四、证明题30设 A,B 为任意集合,E 为全集,证明:B(AB)A)=E。31证明:任何图(无向图或有向图)中,奇度顶点的个数是偶数。32设函数 f:A B,g:BC,f、g 都是双射函数。求证(fog)-1=g-1of-1。五、应用题33在谓词逻辑中构造下面推理的证明:所有不守信用的人都是不可信赖的,有些可以信赖的人是受过教育的。因此,有些受过教育的人是守信用的。(个体域:所有人的集合)34构造欧拉图,其结点数v 和边数 e 满足下述条件:(1)v,e 的奇偶性一样;(2)v,e的奇偶性相反。如果可
29、能,分别画出两个欧拉图;如果不可能,说明原因。模拟试题(五)一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1设 p:天下大雨,q:小王乘公共汽车上班,命题“只有天下大雨,小王才乘公共汽车上班”的符号化形式为()。ApqBqpCpq Dpq2设解释 I 如下,个体域D=a,b,F(a,a)=(b,b)=0,F(a,b)=F(b,a)=1,在解释I 下,下列公式中真值为1 的是()。Ax yF(x,y)B xF(x,y)CxyF(x,y)Dx yF(x,y)3设 G 为 n 阶 m 条边的无向简单图,下列命题为假的是()。AG 一定有生成树Bm 一定
30、大于 n CG 的边色数(G)DG 的最大度(G)n-1 4设 G 为完全二部图K2,3,下面命题中为真的是()。AG 为欧拉图BG 为哈密尔顿图CG 为平面图DG 为正则图5对于任意集合X,Y,Z,则()。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页,共 22 页 -10 AXY=XZY=Z BXY=XZY=Z CXY=X ZY=Z D XY=XZY=Z 6设 Z 是整数集合,“+”是一般加法,则下述函数中不是群 的自同态的是()。Af(x)=xBf(x)=1000 xCf(x)=|x|Df(x)=0 7设 R 为实数集,定义*运算如下:a*b=|a+b+ab|,则*运算满足()
31、。A结合律B交换律C有幺元D幂等律8设 G是一个哈密尔顿图,则G一定是()。A欧拉图 B树 C平面图 D 连通图9下面给出的集合中,哪一个是前缀码?()A0,10,110,101111 B01,001,000,1 Cb,c,aa,ab,aba D 1,11,101,001,0011 10设 G是有 n 个结点 m条边的连通平面图,且有k 个面,则k 等于()。A.m-n+2 Bn-m-2 Cn+m-2 Dm+n+2。11在自然数集N上,下列哪种运算是可结合的?()A a*b=a-b Ba*b=maxa,b Ca*b=a+2b Da*b=|a-b|12集合 A=1,2,10 上的关系 R=|x+
32、y=10,x,yA,则 R满足()。A自反性B对称性 C传递性,对称性 D 传递性13设 P=x|(x+1)24 且 xR,Q=x|5x2+16 且 xR,则下列()正确。A QP B QP CPQ DP=Q 14Q是有理数集,(其中*为普通乘法)不能构成()。A群B独异点 C半群D.交换半群15若一棵完全二元(叉)树有2n-1 个顶点,则它()片树叶。An B2n Cn-1 D 2 二、填空题16含 n 个命题变项的重言式的主合取范式含_个极大项。17在有理数集Q 上定义二元运算“*”,x,yQ 有 x*y=x+y-xy,则关于运算“*”的幺元是。xQ,当 x 1 时,其逆元为。18以 1,
33、1,1,2,2,3 为度数序列的非同构的无向树共有_棵。19已知 n 阶无向简单图G 有 m 条边,则 G 的补图 G 有_条边。20设 R=,则 ranR=_。21设 A=1,2,3,4,则 A 上有 _个不同的双射函数。22任一有向图中,度数为奇数的结点有_个。23令 R(x):x是实数,Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为。24设 G=0,1,2,3,为模 4 加法,群 中的 4 阶元是。三、计算题25设 X=1,2,3,4,若是整数2|,yxyxH3,是正整数,yxyxS,求HSHSH,。26.有向图 D=如下图所示,名师资料总结-精品资料欢迎下载-名师
34、精心整理-第 10 页,共 22 页 -11 27.设 A=x|xR x 0,1。在 A 上定义 6 个函数如下:16151431211,1,1,1,xxxfxxxfxxfxxfxxfxxf令 F为这 6 个函数构成的集合,运算为函数的复合运算。(1)给出运算的运算表。(2)验证 是一个群。28(5 分)设图 G 有一棵树,它有n2个 2 度分支点,n3个 3 度分支点,,nk个 k 度分支点,求G 中叶结点数。四、证明题29设正整数的序偶集合A,在 A 上定义的二元关系R 如下:,Rxv=yu。证明R是一个等价关系。30证明在任何n 阶有向完全图中,所有结点入度的平方之和等于所有结点的出度平
35、方之和。五、应用题31将下列推理符号化并给出形式证明:鸟会飞,猴子不会飞,所以,猴子不是鸟。32)某城市拟在六个区之间假设电话网,其网点间的距离如下带权矩阵给出,试给出架设线路的最优方案,请画出图并计算出线路长。模拟试题(六)五、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1、若 p:他聪明;q:他用功;则“他虽聪明,但不用功”,可符号化为,()A.p q B.p q C.p q D.p q 2、以下命题公式中,为永假式的是,()A.p(pqr)B.(p p)p 求:(1)D 中 v1到 v4的长度为 1,2,3 的通路各有几条?(2)D 中长度
36、3 的通路共有几条?其中几条是回路?名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页,共 22 页 -12 C.(q q)p D.(q p)(p p)3、关于命题变元p 和 q 的大项 M01表示,()。A.p q B.p q C.p q D.p q 4、下列式子正确的是,()A.B.C.D.5、设 R,S 是集合 X=1,2,3,4 上的两个关系,其中R=,S=,。则 S是 R 的()闭包。A.自反B.对称C.传递D.以上都不是6、设 A=a,b,c,则下列是集合A 的划分的是,()A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c 7、.下列不是平面图的是,()8
37、、G 是连通的平面图,有9 个结点,11 个面,则 G 的边数为,()A.16 B.15 C.17 D.18 9、在自然数集N 上,下列哪种*运算是可结合的,()A.a*b=a-bB.a*b=maxa,bC.a*b=a+2bD.a*b=|a-b|10、不能构成代数系统的是,()A.有理数集合Q,x*y=(x+y)/2 B.自然数集合N,x*y=2xyC.AR,x*y=|x-y|D.A=1,-2,3,2,-4,x*y=|y|六、填空题11、已知公式A 含有 3 个命题变项p,q,r,并且它的成假赋值为000,011,110,则 A 的主析取范式为_,A 的主合取范式为_12、令 p:a 能被 4
38、 整除,q:a 能被 2 整除,则命题“只有a 能被 4 整除,a 才能被 2 整除”符号化为_。13、集合,2,2的幂集为 _。14、设 f:R R,f(x)=x2-3x+2,,其中 R 为实数集,则f(1,3)f-1(6)=_ 15、完全二部图K3,4中,点连通度为_,边连通度为_,点色数为_,边色数 为_,匹配数1为_。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页,共 22 页 -13 七、解答题16、使用容斥原理解题:某班有 25 个学生,其中14 人会打篮球,12 人会打排球,6 人会打篮球和排球,5人会打篮球和网球,还有两人会打这三种球。已知6 个会打网球的人都会打篮
39、球或排球。求不会打球的人数。17、给出偏序集 上偏序关系R 的关系图(如下图所示)。(1)求偏序集 的哈斯图。(2)指出 A的最大、最小元(如果有的话),极大、极小元。(3)指出该偏序集是格吗?请说明理由18、一棵树有2n个结点度数为2,3n个结点度数为3,,,kn个结点度数为k,问它有几个度数为 1 的结点。19、已知某系统在通讯联络中只可能出现5 种字符 a,b,c,d,e,其概率分别为0.10,0.22,0.27,0.15,0.26,试画出赫夫曼树并设计赫夫曼编码。20、若 S=1,2,3,19,20,21,设 R 为 S 上的等价关系,且由x y(mod 5)所定义,即x y 能被10
40、 整除。(1)写出由R 导出的 S 的划分;(2)求出商集S/R;(3)设 I 为 S上的恒等关系,试求R I。四、证明题21如果他是计算机系本科生或者是计算机系研究生,那么他一定学过DELPHI 语言而且学过C+语言。只要他学过DELPHI 语言或者C+语言,那么他就会编程序。因此如果他是计算机系本科生,那么他就会编程序。请用命题逻辑推理方法,证明该推理的有效结论。(10 分)22、设 A,B,C是任意集合,证明:(A-B)(B-A)=(A B)-(AB)(5 分)23设 R 是实数集合,S=(a,b)a0,a,b R,利用通常的加法和乘法在S 定义“*”如下:对S中的任意元素(a,b),(
41、c,d)(a,b)*(c,d)=(ac,ad+b)证明 S对“*”运算做成群.(10 分)模拟试题(七)八、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1、已知:已知|G|=18,其某一子群|H|=6,则|G:H|为,()A、18 B、6 C、3 D、不确定值2、公式 p(qp)的类型为,()。a b d c e 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页,共 22 页 -14 A.永真式B.永假式C.可满足式D.一般命题公式3、设解释 R:论域 D 为实数集,a=0,f(x,y)=x-y,A(x,y):xy.则下列公式在 R 下为
42、真的是,()A.xyz(A(x,y)A(f(x,z),f(y,z)B.x A(f(a,x),a)C.xy(A(f(x,y),x)D.xy(A(x,y)A(f(x,a),a)4、设 A=a,a,下列式子中正确的有,()。A.a (A)B.a(A)C.a(A)D.以上都不是5、设集合 A=1,2,3 ,A 上的关系 R=,,则 R 不具有()性质。A.自反性B.对称性C.传递性D.反对称性6、无向图 G 中有 16 条边,且每个结点的度数均为2,则结点数是,()A.8 B.16 C.4 D.32 7、xF(y,x)yG(y)的前束范式为,()A.)(),(yGxzFyx;B.)(),(yGxzFy
43、x;C.)(),(yGxzFyx;D.)(),(xGxzFyx;8、设,Sa b c d,在 S 上定义等价关系abbaIRS,,那么该等价关系对应的划分中有()个划分块。A.1 B.2 C.3 D.49、下列各图不是欧拉图的是,()10、设 Z 为整数集合,*为 Z 上的二元运算,x*y=x+y-3,则 Z 关于*运算构成群,已知5*x=4,则x 为,()A.5/4 B.4/5 C.2 D.3 九、填空题11、已知公式A 含有 3 个命题变项p,q,r,并且它的成假赋值为001,010,100,101,111,则 A 的主析取范式为_,A 的主合取范式为_12、符号化命题:除非a能被 2 整
44、除,否则a 不能被 4 整除。_。13、在一个群 G,*中,若 G中的元素 a 的阶是 k,则 a-1的阶是 _.名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页,共 22 页 -15 14、集合,2,的幂集为 _。15、设 A=,B=1,2,3,则 AB=。16、Q 为有理数集,Q 上定义运算*为 a*b=a+b-ab,则 的单位元是。17、完全二部图K4,5中,点连通度为_,边连通度为_,点色数为_,边色数 为_,匹配数1为_。十、解答题18、对 60 个学生参加课外活动的情况进行调查。结果发现,25 人参加物理小组,26 人参加化学小组,26 人参加生物小组。9 人既参加物理小
45、组又参加生物小组,11 人既参加物理小组又参加化学小组,8 人既参加化学小组又参加生物小组。8 人什么小组也没参加,请回答:(1)有多少人参加了 3 个小组?(2)只参加一个小组的有多少人?。19、无向树 T 有 1 个 2度顶点,3 个 3 度顶点,4 个 4 度顶点,1 个 5 度顶点,其余的都是树叶,则T有几片树叶?20、设 A=1,2,3,4,5,A上偏序关系R=,IA;(1)作出偏序关系 R 的哈斯图(2)令 B=1,2,3,5,求 B 的最大、最小元,极大、极小元,上界,上确界,下界,下确界。21、画出如下所示图的一棵最小生成树,并计算最小生成树的权重。(10 分)22、设 为模
46、6加群,求商群Z6/。四、证明题23、对任意集合A,B,C,证明:(A B)B=A B 24、在一阶逻辑自然推理系统F 中构造下面推理的证明每个喜欢步行的人都不喜欢骑自行车,每个人或者是喜欢骑自行车或者喜欢乘汽车,有的人不喜欢乘汽车,所以有的人不喜欢步行。(个体域为人的集合)。25、设正实数集合R+和实数集合R,+和 x 是普通加法和乘法,定义映射:fRR,,()lnxRf xx,证明,fRR是从到的同构。模拟试题(八)十一、单项选择题在下列每小题的四个备选答案中选出一个正确的答案,并将其字母标号填入题目的括号内。1、若 p:天下大雨;q:他乘公共汽车上班;则“除非天下大雨,否则他不乘公共汽车
47、 上班。”可符号化为,()A.p q B.p q C.p q D.qp2、)(),(yyGxyxF的前束范式为,()名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页,共 22 页 -16 A.)(),(yGxyFyx;B.)(),(yGxzFyx;C.)(),(yGxzFxy;D.),(),(yxGzxFyx;3、设谓词 P(x):x 是奇数,Q(x):x 是偶数,谓词公式x(P(x)Q(x)在哪个个体域中为真()A.自然数 B.实数C.复数D.A-C均成立4、令 F(x):x 是兔子,G(x):x 是乌龟,H(x,y):x 比 y 跑得快,命题“并不是所有的兔子比乌龟跑得快”可以符
48、号化为,()A.),()()(yxHyGxFyx;B.),()()(yxHyGxFyx;C.),()()(yxHyGxFyx;D.),()()(yxHyGxFyx5、设,1,1,2S,则)(SP有()个元素A.3 B.16 C.6 D.86、设3,2,1S,左图是S上关系 R1的关系图,则它具有()性质.A.自反的,对称的,传递的;B.反自反的,反对称的;C.自反的,传递的;D.自反的;7、设,RV,其中为普通乘法,对任意Rx令xx2)(1,22)(xx,xx1)(3,xx)(4,则其中有()个是V的自同态,A.0 B.1 C.2 D.3 8、设 Z 是整数集合,则下面定义的二元运算不能使Z
49、与构成代数系统的是()A.ij=|i-j|,i,j Z B.ij=i j-j2,i,jZ C.ij=i/j,i,j Z D.ij=i2+j2+1,i,j Z 9、设,G是群,Gba,则下列结论不正确的是,()A.111)(ababB.bax有惟一解C.yxayax则,D.baab10、设无向图G有 16 条边且每个顶点的度数都是2,则图 G有()个顶点。A.10 B.4 C.17 D.16 十二、填空题11、命题公式rqp)(的主析取范式中含极小项的个数为_,成真赋值为_。12、令 F(x):x 是人。G(x):x 犯错误。则命题“没有不犯错误的人”符号化为_ 13、设n阶无向简单图G中,1)
50、(nG,问)(G为_.14、素数阶群一定是_群,它的生成元是 _。15、全二部图)1,1(,mnKmn都是欧拉图,这个命题的真值为_;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页,共 22 页 -17 16、群,为模 6 加法运算,则子群 H 0,2,4 的所有的右陪集为_,_.17、集合 A 的一个划分,确定A 的元素间的关系为_ 18、设 Z 是整数集,在Z 上定义二元运算*为 a*b=a+b+a b,其中+和是数的加法和乘法,则代数系统 的幺元是,零元是。十三、解答题19、求rqp)(的主析取范式和主合取范式。20、用容斥原理解题:某班级有学生四十名,共有三门选修课可供选择