离散数学试卷七试题与附标准答案

《离散数学试卷七试题与附标准答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、试卷七试题与答案一、填空1、n阶完全图Kn的边数为。2、右图的邻接矩阵A=。3、完全二叉树中，叶数为nt，则边数m=。4、设<{a,b,c},*>为代数系统，*运算如下：*abcaabcbbaccccc则它的幺元为；零元为；a、b、c的逆元分别为。5、任何图的点连通度，边连通度，最小点度的关系为。6、在具有n个结点的有向图中，任何基本通路的长度都不超过。7、结点数n（）的简单连通平面图的边数为m，则m与n的关系为。8、若对命题P赋值1，Q赋值0，则命题的真值为。9、命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号

2、化为。10、若关系R是等价关系，则R满足性质。二、选择1、左边图的补图为（）。1、对左图G，则分别为（）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。2、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（）片树叶。A、3；B、4；C、5；D、63、设是代数系统，其中+，·为普通的加法和乘法，则A=（）时是整环。A、；B、；C、；D、。4、设A={1，2，…，10}，则下面定义的运算*关于A封闭的有（）。A、x*y=max(x,y)；B、x*y=质数p的个数使得

3、；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为真，且使公式也为真，则解释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、一个割边集与任何生成

4、树之间（）。A、没有关系；B、割边集诱导子图是生成树；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是阶数

5、不小于11的简单图，则G或中至少有一个是非平图。4、用构造证明法证明，，Þ。二、生成树及应用1、如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。　　矚慫润厲钐瘗睞枥庑赖。2、）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。聞創沟燴鐺險爱氇谴净。三、对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N”。MaxMin+可结合性可交换性存在幺元

6、存在零元答案一、填空1、；2、；3、；4a，c，a、b、没有5、n-1；6、；7、；8、0；9、；10、5、自反性、对称性、传递性；一、选择题目12345678910答案AACDA，CACDBD三、1.解：∴使公式的值为F的成真赋值为：；；。A2349B24710122．解：则R的关系图为：R的关系矩阵为关系R不是A到B的函数，因为元素2，4的象不唯一（或元素9无象）。3、解：（1）1），即运算*是封闭的。2）而，即*可结合。3）设S关于*有幺元e，则。而。4）设有逆元。则，即，，即S中任意元都有逆元，综上得出，构成群。（2）由，。4、解：

7、原式。5、解：①A中最大元为，最小元不存在；②上界，上确界；下界无，下确界无。四、证明i.设G=（V，E），对完全二部图有当时，完全二部图的边数m有最大值。故对任意简单二部图有。ii.反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然。残骛楼諍锩瀨濟溆塹籟。与假设矛盾。所以G连通。3、（1）当n=11时，边数条，因而必有或的边数大于等于28，不妨设G的边数，设G有k个连通分支，则G中必有回路。（否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则,酽锕极額閉镇桧猪訣锥。矛盾）下面用

8、反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由g()条边围成，由点、边、面数的关系，得：彈贸摄尔霁毙攬砖卤庑。而矛