《离散数学试卷七试题与附标准答案》由会员分享，可在线阅读，更多相关《离散数学试卷七试题与附标准答案（7页珍藏版）》请在金锄头文库上搜索。
1、试卷七试题与答案一、 填空1、 n阶完全图Kn的边数为。2、 右图的邻接矩阵A= 。3、 完全二叉树中，叶数为nt，则边数m= 。4、 设为代数系统，* 运算如下：*abcaabcbbaccccc则它的幺元为；零元为；a、b、c的逆元分别为。5、任何图的点连通度，边连通度，最小点度的关系为。6、在具有n个结点的有向图中，任何基本通路的长度都不超过。7、结点数n（）的简单连通平面图的边数为m，则m与n的关系为。8、若对命题P赋值1，Q赋值0，则命题的真值为。9、命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为。10、若关系R是等价关系，则R满足性质。二、 选择1、
2、 左边图的补图为（）。2、 对左图G，则分别为（）。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、64、 设是代数系统，其中+，为普通的加法和乘法，则A=（）时是整环。A、； B、；C、； D、。5、 设A=1，2，10 ，则下面定义的运算*关于A封闭的有（）。A、 x*y=max(x ,y)； B、x*y=质数p的个数使得；C、x*y=gcd(x , y)； (gcd (x ,y)表示x和y的最大公约数)；D、x*y=lcm(x ,y
3、) （lcm(x ,y) 表示x和y的最小公倍数）。6、如果解释I使公式A为真，且使公式也为真，则解释I使公式B为（）。A、真； B、假； C、可满足； D、与解释I无关。7、设，则P（A）A = （）。 A、A ； B、P（A）； C、；D、。8、设集合A，B是有穷集合，且，则从A到B有（）个不同的双射函数。 A、； B、； C、； D、。9、设K = e , a , b , c，是Klein四元群，则元素a的逆元为（）。 A、e ； B、a ； C、b ； D、c。10、一个割边集与任何生成树之间（）。A、没有关系； B、割边集诱导子图是生成树； C、有一条公共边； D、至少有一条公共边。
4、三、 计算1、通过主合取范式，求出使公式的值为F的成真赋值。2、设，从A到B的关系，试给出R的关系图和关系矩阵，并说明此关系是否为函数？为什么？3、设S = R - -1（R为实数集），。（1）说明是否构成群；（2）在中解方程。4、将公式划为只含有联结词的等价公式。5、设，偏序集的Hass图为求 A中最小元与最大元；的上界和上确界，下界和下确界。四、 证明1、设G是（n,m）简单二部图，则。2、设G为具有n个结点的简单图，且则G是连通图。3、设G是阶数不小于11的简单图，则G或中至少有一个是非平图。4、用构造证明法证明，。五、 生成树及应用1、如下图所示的赋权图表示某七个城市及预先测算出它们之
5、间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。矚慫润厲钐瘗睞枥庑赖。2、）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPY NEW YEAR的编码信息。聞創沟燴鐺險爱氇谴净。六、对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMin+可结合性可交换性存在幺元存在零元答案一、 填空1、；2、；3、；4a，c，a、b、没有5、n-1 ；6、；7、；8、0； 9、；10、5、自反性、对称性、传递性；二、 选择题目12345678910答案AACDA，CACDB
6、D三、1. 解：使公式的值为F的成真赋值为：；。A2349B24710122解：则R的关系图为：R的关系矩阵为关系R不是A到B的函数，因为元素2，4的象不唯一（或元素9无象）。3、解：（1）1），即运算*是封闭的。 2）而，即*可结合。 3）设S关于*有幺元e，则。而。4）设有逆元。则，即，即 S中任意元都有逆元，综上得出，构成群。（2）由，。4、解：原式。5、解： A中最大元为，最小元不存在；上界，上确界；下界无，下确界无。四、 证明i. 设G=（V，E），对完全二部图有当时，完全二部图的边数m有最大值。故对任意简单二部图有。ii. 反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，
7、假设G1和G2的顶点数分别为n1和n2，显然。残骛楼諍锩瀨濟溆塹籟。与假设矛盾。所以G连通。3、（1）当n=11时，边数条，因而必有或的边数大于等于28，不妨设G的边数，设G有k个连通分支，则G中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则,酽锕极額閉镇桧猪訣锥。矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3 。于是G的每个面至少由g ()条边围成，由点、边、面数的关系，得：彈贸摄尔霁毙攬砖卤庑。而矛盾，所以G为非平面图。（2）当n11时，考虑G的具有11个顶点的子图，则或必为非平面图。如果为非平面图，则为非平面
8、图。如果为非平面图，则为非平面图。4、证明：（1） B P(附加前提)（2）前提引入 (3) (1)(2)假言推理 (4) A (3)化简 (5) 前提引入 (6) (4)(5)假言推理 (7) C (6)化简 (8) 前提引入 (9) (7)(8)拒取式 (10) (9)置换 (11) E (10)化简五、 树的应用1、解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价五、由二叉树知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六、MaxMin+可结合性YYY可交换性YYY存在幺元NNY存在零元NNN
