《离散数学试卷七试题与答案》由会员分享，可在线阅读，更多相关《离散数学试卷七试题与答案（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是等价关系，那
2、么R满足 性质。二、 选择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、设，那么PAA = 。 A、A ； B、PA； 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 - -1R为实数集，。 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，CACDBD三、1. 解：使公式的值
6、为F的成真赋值为： ； ； 。A2349B24710122解：那么R的关系图为：R的关系矩阵为 关系R不是A到B的函数，因为元素2，4的象不唯一或元素9无象。3、解：11，即运算*是封闭的。 2 而，即*可结合。 3设S关于*有幺元e，那么。而 。4设有逆元。那么，即 ，即 S中任意元都有逆元，综上得出，构成群。2由， 。4、解：原式 。5、解： A中最大元为，最小元不存在； 上界，上确界；下界无，下确界无。四、 证明 i. 设G=V，E，对完全二部图有当时，完全二部图的边数m有最大值。故对任意简单二部图有。ii. 反证法：假设G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶
7、点数分别为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个顶点的子图，那么或必为非平面图。如果为非平面图，那么为非平面图。如果为非平面图，那么为非平面图。4、证明：1 B P(附加前提) 2 前提引入
8、 (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
