《离散数学试卷七试题与答案》由会员分享，可在线阅读，更多相关《离散数学试卷七试题与答案（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
2、满足 性质。二、 选择1、 左边图的补图为（ ）。 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的最
3、大公约数)；D、x*y=lcm(x ,y) （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、割边集诱导子图是生
4、成树； C、有一条公共边； D、至少有一条公共边。三、 计算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、用构造证明法证明，。五、 生成树及
5、应用 1、如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。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答案
6、AACDA，CACDBD三、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
7、不连通，不妨设G可分成两个连通分支G1、G2，假设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
离散数学试卷七试题与答案
