《2022年离散数学试卷七试题与答案 .pdf》由会员分享，可在线阅读，更多相关《2022年离散数学试卷七试题与答案 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 7 试卷七试卷与答案一、填空1、 n 阶完全图 Kn的边数为。2、 右图的邻接矩阵A= 。3、 完全二叉树中，叶数为nt，则边数 m= 。4、 设 为代数系统， * 运算如下：则它的幺元为；零元为；a、b、c的逆元分别为。)(G，边连通度)(G，最小5 、 任 何 图 的 点 连 通 度点度)(G的关系为。6、在具有 n 个结点的有向图中，任何基本通路的长度都不超过。7、结点数 n（3n）的简单连通平面图的边数为m，则 m 与 n 的关系为。8、若对命题P赋值 1，Q 赋值 0，则命题QP的真值为。9、命题“如果你不看电影，那么我也不看电影”（P：你看电影， Q：我看电影）的符号化为。
2、10、若关系 R 是等价关系，则R 满足性质。二、选择1、 左边图的补图为（）。2、 对左图 G，则)(),(),(GGGk分别为（）。* a b c a a b c b b a c c c c c 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页2 / 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、 设是代数系统，其中+，为普通的加法和乘
3、法，则A=（）时 是整环。A、,2|Znnxx； B、,12|Znnxx；C、,0|Zxxx且； D、,5|4Rbabaxx。5、 设 A=1 ，2， 10 ，则下面定义的运算*关于 A 封闭的有（）。A、 x*y=max(x ,y) ； B、x*y= 质数 p的个数使得ypx；C、x*y=gcd(x , y) ； (gcd (x ,y) 表示 x 和 y 的最大公约数 )；D、x*y=lcm(x ,y) （lcm(x ,y) 表示 x和 y的最小公倍数）。6、如果解释I 使公式 A 为真，且使公式BA也为真，则解释I 使公式 B 为（）。A、真； B、假； C、可满足； D、与解释 I 无关
4、。7、设baA,，则 P（A） A = （）。 A、A ； B、P（A）； C、bAaAbbabbaaaba,；D、AbAabbbaabaaba, , , , ,。8、设集合A，B 是有穷集合，且nBmA,，则从 A 到 B 有（）个不同的双射函数。 A、n； B、m； C、!n； D、!m。9、设 K = e , a , b , c ，,K是 Klein 四元群，则元素a的逆元为（）。 A、e ； B、a ； C、b ； D、c。10、一个割边集与任何生成树之间（）。A、没有关系； B、割边集诱导子图是生成树； C、有一条公共边； D、至少有一条公共边。三、计算1、通过主合取范式，求出使公式
5、RQP)(的值为 F 的成真赋值。2、设9432，A，12,10742，B，从 A 到 B 的关系,baBbAabaR整除且，试给出R 的关系图和关系矩阵，并说明此关系是否为函数？为什么？3、设 S = R - -1 （R 为实数集），abbaba。（1）说明,S是否构成群；（ 2）在S中解方程732x。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页3 / 7 4、将公式)()(RPRQP）划为只含有联结词，的等价公式。5、设,54321xxxxxA，偏序集RA,的 Hass图为求 A 中最小元与最大元；,543xxx的上界和上
6、确界，下界和下确界。四、证明1、设 G 是（ n,m）简单二部图，则42nm。2、设 G 为具有 n 个结点的简单图，且)2)(1(21nnm则 G 是连通图。3、设 G 是阶数不小于11 的简单图，则G或G中至少有一个是非平图。4、用构造证明法证明)(CBA，CFE)(，)(SABEB。五、生成树及应用1、如下图所示的赋权图表示某七个城市721,vvv及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。2、）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW YEAR 的编码信息。六、
7、对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y ”或“N”。Max Min + 可结合性可交换性存在幺元存在零元答案一、填空精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页4 / 7 1、)1(21nn；2、0110001011001010；3、) 1(2tn；4a，c，a、b、没有5、n-1 ；6、)()()(GGG；7、63nm；8、0； 9、QP；10、5、自反性、对称性、传递性；二、选择题目1 2 3 4 5 6 7 8 9 10 答案A A C D A，C A C D B D 三、1.
8、 解：010110100)()()()()()()()(MMMRQPRQPRQPRQPRQRPRQPRQP原式使公式RQP)(的值为 F 的成真赋值为：0:0:1:RQP；0:1:1:RQP；0:1:0:RQP。2解：12,4,4,4,12,3,12,2,10,2,4,2,2,2R则 R 的关系图为：R 的关系矩阵为00000100101000011011RM关系 R 不是 A 到 B 的函数，因为元素 2，4 的象不唯一（或元素9 无象）。3、解：（ 1）1）SabbabaSba易证,，即运算 *是封闭的。 2）Scba,)()()(abcbcacabcbacabbacabbacabbacb
9、a而,)()()()(abcacabbccbabccbabccbabccbacba)()(cbacba，即 * 可结合。A 2 3 4 9 B 2 4 7 10 12 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 7 页5 / 7 3）设 S关于 * 有幺元 e，则aeaaeSa,。而0,eaeaeaaeea。4）Sa设有逆元1a。则eaaaa11，即011aaaa，aaa11，即 S 中任意元都有逆元，综上得出，,S构成群。（2）由7111266323232xxxxxx，31x。4、解：原式)()()()(RPRQPRPRQP)()
10、(RPRQP。5、解： A 中最大元为1x，最小元不存在；,543xxx上界31,xx，上确界1x；下界无，下确界无。四、 证明i.设 G=（V，E），nnnnYnXYXV2121,则对完全二部图有4)2()(2211211121nnnnnnnnnnnm当21nn时，完全二部图),(mn的边数 m 有最大值42n。故对任意简单二部图),(mn有42nm。ii.反证法：若G 不连通，不妨设G 可分成两个连通分支G1、G2，假设 G1和 G2的顶点数分别为 n1和 n2，显然nnn21。11112121nnnnnn2)2)(1(2)2)(1(2) 1(2)1(212211nnnnnnnnnm与假设
11、矛盾。所以G 连通。3、（ 1）当 n=11 时，11KGG11K边数5521011m条，因而必有G或G的边数大于等于 28，不妨设 G 的边数28m，设 G 有 k 个连通分支，则G 中必有回路。（否则G 为 k 棵树构成的森林，每棵树的顶点数为ni，边数 mi，则1, 1kinmii,mmnnkiikii11,11精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页6 / 7 kiikiikknnmm1111)1(28矛盾）下面用反证法证明G 为非平面图。假设 G 为平面图，由于G 中有回路且G 为简单图，因而回路长大于等于3 。
12、于是 G 的每个面至少由g (3g)条边围成，由点、边、面数的关系)1(2knggm，得：2723113)11(11(3)1(11(133)111(228kkggm而2728矛盾，所以G 为非平面图。（2）当 n11 时，考虑 G 的具有 11个顶点的子图G，则G或G必为非平面图。如果G为非平面图，则G为非平面图。如果G为非平面图，则G为非平面图。4、证明：（ 1） B P(附加前提 ) （2）)(SAB前提引入 (3) SA(1)(2) 假言推理 (4) A (3) 化简 (5) CBA前提引入 (6) CB (4)(5)假言推理 (7) C (6) 化简 (8) CFE)(前提引入 (9)
13、 )(FE (7)(8)拒取式 (10) FE (9)置换 (11) E (10)化简五、 树的应用1、解：用库斯克（Kruskal ）算法求产生的最优树。算法略。结果如图：树权 C(T)=23+1+4+9+3+17=57 即为总造价五、由二叉树知精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 7 页7 / 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 页