离散数学试题八考试题与答案.doc

《离散数学试题八考试题与答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试卷八试卷与答案一、填空15%<每小题3分）1、n阶完全图Kn的边数为。2、右图的邻接矩阵A=。3、图的对偶图为。4、完全二叉树中，叶数为nt，则边数m=。5、设<{a,b,c},*>为代数系统，*运算如下：*abcaabcbbaccccc则它的幺元为；零元为；a、b、c的逆元分别为。二、选择15%<每小题3分）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、设是代数系统

2、，其中+，·为普通的加法和乘法，则A=<）时是整环。A、；B、；C、；D、。5、设A={1，2，…，10}，则下面定义的运算*关于A封闭的有<）。6/6A、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>表示x和y的最小公倍数）。一、证明45%1、设G是

3、电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：b5E2RGbCAP+01·01001000110101证明它是一个环，并且是一个域。<15分）二、生成树及应用10%1、<10分）如下图所示的赋权图表示某七个城市及预先测算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间既能够通信而且总造价最小。　　p1EanqFDPw2、<10分）构造H、A、P、N、E、W、R、对应的前缀码，并画出与该前缀码对应的二叉树，写出英文短语HAPPYNEWYEAR的编码信息。DXDiTa9E3d三、5%对于实数集合R，在下表所列的二元远算是否具有左边一列中的性质，请在

4、相应位上填写“Y”或“N”。MaxMin+可结合性可交换性6/6存在幺元存在零元答案：一、填空15%<每小题3分）1、；2、；3、；4、；5、a，c，a、b、没有二、选择15%<每小题3分）题目12345答案AACDA，C三、证明45%1、<8分）：设G=

5、k个连通分支，则G中必有回路。<否则G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则,5PCzVD7HxA6/6矛盾）下面用反证法证明G为非平面图。假设G为平面图，由于G中有回路且G为简单图，因而回路长大于等于3。于是G的每个面至少由g(>条边围成，由点、边、面数的关系，得：jLBHrnAILg而矛盾，所以G为非平面图。<2）当n>11时，考虑G的具有11个顶点的子图，则或必为非平面图。如果为非平面图，则为非平面图。如果为非平面图，则为非平面图。4、<15分）1）[{0，1}，+，·]是环①[{0，1}，+]是交换群乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交

6、换。群：<0+0）+0=0+<0+0）=0；<0+0）+1=0+<0+1）=1；<0+1）+0=0+<1+0）=1；<0+1）+1=0+<1+1）=0；<1+1）+1=1+<1+1）=0……结合律成立。幺：幺元为0。逆：0，1逆元均为其本身。所以，<{0，1}，+>是Abel群。②<{0，1}，·>是半群乘：由“·”运算表知封闭群：(0·0>·0=0·<0·0）=0；<0·0）·1=0·<0·1）=1；<0·1）·0=0·<1·0）=1；<0·1）·1=0·<1·1）=0；<1·1）·1=1·<1·1）=0；…③·对+的分配律对Ⅰ0·+(0·y>6/6

7、Ⅱ1·=0则当<）则所以均有同理可证：所以·对+是可分配的。由①②③得，<{0，1}，+，·>是环。<2）<{0，1}，+，·>是域因为<{0，1}，+，·>是有限环，故只需证明是整环即可。①乘交环：由乘法运算表的对称性知，乘法可交换。②含幺环：乘法的幺元是1③无零因子：1·1=1≠0因此[{0，1}，+，·]是整环，故它是域。一、树的应用20%1、<10分）解：用库斯克