2022年离散数学试卷七试题与答案.docx
精选学习资料 - - - - - - - - - 试卷七试卷与答案一、填空1、 n 阶完全图 K n的边数为；2、 右图的邻接矩阵 A= ；3、 完全二叉树中,叶数为 nt,就边数 m= ；4、 设 < a,b,c, * > 为代数系统, * 运算如下：点度就它的幺元为；零元为；* a b c G,边连通度G,最小a、b、 c的逆元分别为；a a b c 5 、 任 何 图 的 点 连 通 度b b a c c c c c G 的关系为；6、在具有 n 个结点的有向图中,任何基本通路的长度都不超过；7、结点数 n（n 3）的简洁连通平面图的边数为 m,就 m 与 n 的关系为；8、如对命题 P 赋值 1, Q 赋值 0,就命题 P Q 的真值为；9、命题“ 假如你不看电影,那么我也不看电影” （P：你看电影, Q：我看电影）的符号化为10、如关系 R 是等价关系,就 R 满意性质；二、挑选1、 左边图的补图为（）；2、 对左图 G,就kG,G,G分别为（）；名师归纳总结 - - - - - - -第 1 页,共 7 页精选学习资料 - - - - - - - - - A、 2、 2、2； B、 1、1、2； C、 2、1、2； D、 1、2、2 ；3、 一棵无向树T 有 8 个顶点, 4 度、 3 度、 2 度的分枝点各1 个,其余顶点均为树叶,就T 中有（）片树叶；A、 3； B、 4； C、5； D、 6 4、 设 <A , +,·>是代数系统,其中+,· 为一般的加法和乘法,就A=（）时 <A, + ,·>是整环；A、 x | x 2 n , n Z ； B、 x | x 2 n 1 , n Z ；C、 x | x 0 , 且 x Z ； D、 x | x a b 4 5 , a , b R ；5、 设 A=1 , 2, , 10 ,就下面定义的运算 *关于 A 封闭的有（）；A、 x*y=maxx ,y ； B、x*y= 质数 p的个数使得 x p y；C、x*y=gcdx , y ； gcd x ,y 表示 x 和 y 的最大公约数 ；D、 x*y=lcmx ,y （lcmx ,y 表示 x 和 y 的最小公倍数）；6、假如说明I 使公式 A 为真,且使公式AB也为真,就说明I 使公式 B 为（）；A 、真； B、假； C、可满意； D、与说明 I 无关；7、设Aa ,b,就 P（A ）× A = （）； A、A ； B、P（A ）； C、,a,b,a ,a,a ,b,b ,a,b ,b,A ,a,A ,b；、Db ,a ,a ,b ,b ,b ,a ,A,b ,A；a ,b ,a ,a ,8、设集合A, B 是有穷集合,且Am,Bn,就从 A 到 B 有（）个不同的双射函数；m ； A、 n； B、 m； C、n ； D、9、设 K = e , a , b , c ,K,是 Klein 四元群,就元素a的逆元为（）； A、e ； B、a ； C、b ； D、 c；10、一个割边集与任何生成树之间（）；A 、没有关系； B、割边集诱导子图是生成树； C、有一条公共边； D、至少有一条公共边；三、运算1、通过主合取范式,求出访公式PQR的值为 F 的成真赋值；2,4,7,10,12,从 A 到 B 的关系2、设A2,3,4,9 ,BB,且a整除b ,试给出R 的关系图和关系矩阵,并说明此关系是Ra,baA,b否为函数？为什么？3、设 S = R - -1 （ R 为实数集）,ababab；37；（1）说明S,是否构成群；（ 2）在 S 中解方程2x2 / 7 名师归纳总结 - - - - - - -第 2 页,共 7 页精选学习资料 - - - - - - - - - 4、将公式P,xQ,R）5PR划为只含有联结词, 的等价公式；5、设Ax 12,x 3x 4,x,偏序集A,R的 Hass图为求 A 中最小元与最大元；x3,x 4,x5的上界和上确界,下界和下确界；证明四、1、设 G 是（ n,m）简洁二部图,就mn2；BE；42、设 G 为具有 n 个结点的简洁图,且m1n1 n2就 G 是连通图；23、设 G 是阶数不小于11 的简洁图,就G或 G中至少有一个是非平图；4、用构造证明法证明ABC,EFC,BAS五、生成树及应用1、如下图所示的赋权图表示某七个城市v 1,v2,v7及预先测算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间既能够通信而且总造价最小；2、）构造 H、 A、P、 N、 E、W、R、对应的前缀码,并画出与该 前缀码对应的二叉树,写出英文短语 HAPPY NEW YEAR 的编码 信息；六、对于实数集合R,在下表所列的二元远算是否具有左边一列中的性质,请在相应位上填写“Y ” 或“ N” ；Max Min + 可结合性 可交换性 存在幺元 存在零元答案 一、填空3 / 7 名师归纳总结 - - - - - - -第 3 页,共 7 页精选学习资料 - - - - - - - - - 01011、1nn1 ； 2、00118 9 10 01000110； 3、2 tn1； 4a, c,a、 b、没有2GG； 7、m3n6；5、n-1 ；6、G8、0； 9、PQ； 10、5、自反性、对称性、传递性；1 2 3 4 5 6 7 二、挑选题目答案A A C D A ,C A C D B D 三、1. 解：原式PQRPQRPR QR QR PQR PQR PQR PM100M110M010,4,12使公式PQR的值为 F 的成真赋值为：P:1P:1P:0Q:0Q:1Q:1R:0；R:0；R:0；2解：R2,2,2,4,2,10,2,12,3,12,4,4就 R 的关系图为：A B R 的关系矩阵为2 110112 4 MR000013 010014 7 10 00000关系 R 不是 A 到 B 的函数,由于9 12 元素 2, 4 的象不唯独（或元素9 无象）；3、 解：（ 1） 1）a ,bS易证abababS,即运算 *是封闭的； 2）a ,b ,cSabcababcababcababcabcabacbcabc,而abc abcbcabcbcabcbcab cabcbcabacabc,abc,即 * 可结合；4 / 7 名师归纳总结 - - - - - - -第 4 页,共 7 页精选学习资料 - - - - - - - - - 3）设 S关于 * 有幺元 e,就 a S , e a a e a；而 a e e a a e ea a , e 0；4）a S 设有逆元 a 1；就 a a 1 a 1 a e,1 a1 1 a即 a a aa 0,1 a,即 S 中任意元都有逆元,综上得出,S , 构成群；（ 2）由 2 x 3 2 x 3 2 x 3 x 6 6 x 12 x 11 7,1x3；4、 解：原式 P Q R P R P Q R P R P Q R P R ；5、解： A 中最大元为 x ,最小元不存在； x 3 , x 4 , x 5 上界 x 1, x 3,上确界 1x；下界无,下确界无；四、 证明i. 设 G=（ V, E）,V X Y , X n 1 , Y n 2 , 就 n 1 n 2 n22 n 2 nm n 1 n 2 n 1 n n 1 n 1 n 1 n n 1 对完全二部图有 2 42当 n 1 n2 时,完全二部图 n , m 的边数 m 有最大值 n4；2n故对任意简洁二部图 n , m 有 m4；ii. 反证法：如 G 不连通,不妨设 G 可分成两个连通分支 G1、 G2,假设 G1和 G2的顶点数分别为 n1 和 n2,明显 n 1 n 2 n；n 1 1 n 2 1 n 1 n 1 n 2 n 1m n 1 n 1 1 n 2 n 2 1 n 1 n 1 n 2 2 n 1 n 2 2 2 2 2与假设冲突；所以 G 连通；' 11 103、（ 1）当 n=11 时,G G K 11 K 11 边数 m2 55条,因而必有 G 或 G 的边数大于等于 28,不妨设 G 的边数 m 28,设 G 有 k 个连通分支,就 G 中必有回路；（否就 G 为 k 棵树构成的森k k林,每棵树的顶点数为 ni,边数 mi,就 m i n i ,1 i 1 k , i 1 n i n 11 ,i 1 m i m5 / 7 名师归纳总结 - - - - - - -第 5 页,共 7 页精选学习资料 - - - - - - - - - 28mik1miikni1 nk11k冲突）1下面用反证法证明 G 为非平面图；假设 G 为平面图,由于 G 中有回路且 G 为简洁图,因而回路长大于等于 3 ；于是 G 的每个面至少由gm n k 1 g g 3 条边围成,由点、边、面数的关系 g 2,得：g 328 m 11 k 1 11 k 1 3 11 1 1 3 11 3 2 27g 2 3 1而 28 27 冲突,所以 G 为非平面图；' ' '（ 2）当 n>11 时,考虑 G 的具有 11 个顶点的子图 G ,就 G 或 G必为非平面图；'假如 G 为非平面图,就 G 为非平面图；'假如 G为非平面图,就G为非平面图；4、证明：（ 1） B P附加前提 （2）BAASS 前提引入 3 12 假言推理 4 A 3 化简 5 ABC前提引入 6 BC 45假言推理 7 C 6 化简 8 EEFFC前提引入 9 F 78拒取式 10 E 9 置换 11 E 10化简五、 树的应用1、解：用库斯克（Kruskal ）算法求产生的最优树；算法略；结果如图：树权 CT=23+1+4+9+3+17=57 即为总造价五、由二叉树知6 / 7 名师归纳总结 - - - - - - -第 6 页,共 7 页精选学习资料 - - - - - - - - - H、 A、 P、Y 、N、 E、W、R 对应的编码分别为000、001、 010、011、 100、101、110、 111；明显 000 ,001,010,011,100, 101, 110, 111 为前缀码；英文短语 HAPPY NEW YEAR 的编码信息为000 001 010 010 011 100 101 001 001 101 001 111 六、可结合性Max Min + Y Y Y 可交换性Y Y Y 存在幺元N N Y 存在零元N N N 7 / 7 名师归纳总结 - - - - - - -第 7 页,共 7 页
