四、计算22%
1、在二叉树中
1） 求带权为2，3，5，7，8的最优二叉树T。（5分） 2） 求T对应的二元前缀码。（5分）
2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。
答案：
一、填空（15%）每空3 分
1、 6；2、n；3、2；4、+对·分配且·对+分配均成立；5、a?a?a且a?a?a。
二、选择（15%）每小题3分
题目 答案
1 A,B 2 B,D 3 B 4 C 5 D 三、证明（48%）
1、（10分）证明：用n个顶点v1，?，vn表示n个人，构成顶点集V={v1，?，vn}，设
E?{uv|u,v?V,且u,v是朋友（u?v）}，无向图G=（V，E）
现证G中至少有两个结点度数相同。
事实上，（1）若G中孤立点个数大于等于2，结论成立。
（2） 若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n顶点其度数取值只能是1，2，?，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。 2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。
3（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8
由图论基本定理知：
?deg(F)?2?m?24，而deg(F)?3，所以必有deg(F)?3，即
ii每个面用3条边围成。
4（10分） 证：设循环群[A，·]的生成元为a，同态映射为f，同态像为[f（A），*]，于是
?an,am?A都有f(an?am)?f(an)*f(am)
对n=1有f(a)?f(a)
n=2, 有f(a)?f(a?a)?f(a)*f(a)?(f(a)) 若n=k-1时 有f(akk?122)?(f(a))k?1
k?1对n=k时，f(a)?f(a?a)?f(ak?1)*f(a)?(f(a))k?1*f(a)?(f(a))k
n(f(a))这表明，f(A)中每一个元素均可表示为，所以[f(A),*]为f(a) 生成的循环群。
5、证：
（1） 交换律：?a,b?B有 a*b?(a?b)?(a?b)?(b?a)?(b?a)?b*a （2） 结合律：?a,b,c?B有
(a*b)*c?((a?b)?(a?b))*c?(((a?b)?(a?b))?c)?((a?b)?(a?b))?c?(a?b?c?a?b?c)?((a?b)?(a?b))?c?a?b?c?a?b?c?(a?a?a?b?b?a?b?b)?c?a?b?c?a?b?c?b?a?c?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c而：
a*(b*c)?a*((b?c)?(b?c))?(a?(b?c)?(b?c))?((a?(b?c)?(b?c))?a?(b?c)?(b?c)?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c?(a*b)*c?a*(b*c)
（3） 幺：?a?B有
a*0?(a?0)?(a?0)?a?0?a0*a?(0?a)?(0?a)?0?a?a
?0是[B，*]幺元。
（4） 逆：?a?B a*a?(a?a)?(a?a)?0?0?0
?a是a的逆元。
综上所述：[B，*]是阿贝尔群。
四、计算（22%）
1、（10分）
（1）（5分）由Huffman方法,得最佳二叉树为：
（2）（5分）最佳前缀码为：000，001，01，10，11 2、（12分）
图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF 复制道路EG、GF，得图G，则G是欧拉图。 由D开始找一条欧拉回路：DEGFGEBACBDCFD。 道路长度为：
35+8+20+20+8+40+30+50+19+6+12+10+23=281。
试卷六试题与答案
‘
‘
一、 填空 15% （每小题 3分）
1、 n阶完全图结点v的度数d(v) = 。
2、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶
点，Nk+1个k+1度顶点，则N k = 。 3、 算式 ((a?(b*c)*d)?(e*f)的二叉树表示为
。 4、 如图
给出格L，则e的补元是 。
5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元
是 。
二、选择 15% （每小题 3分）
1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（ ）。
A、群；B、环；C、域；D、格。 2、设[{a , b , c}，*]为代数系统，*运算如下：
* a b c 则零元为（ ）。
A、a； B、b； C、c； D、没有。
a a b c b b a c c c c c 3、如右图 相对于完全图K5的补图为（ ）。
4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）
4度结点。
A、1； B、2； C、3； D、4。
5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A，
+，·]是整环。
A、{x|x?2n,n?Z}； B、{x|x?2n?1,n?Z}；
4C、{x|x?0,且x?Z}； D、{x|x?a?b5,a,b?R}。