第七章习题参考答案

第七章习题解答1分析①计算总度数.n阶无向树的边数m=n-1,由握手定理可知i=1n②构造可能的度数列.将2n-2划分成n份，第i份为对应顶点vi数d(vi),1≤d(v③按每一个度数列画树.按不同的度数列画出的树都是不同构的，对同一个度数列可能画出多棵非同构的树.本题中：(1)n=5,m=4,度数之和为8.将8划分成3份的方案为：①1,1,1,1,4;②1,1,1,2,3;③1,1,2,2,2.每种方案都只有1棵非同构的树，共3棵非同构树，如图7-9.图7-9(2)n=7,m=6①1,1,1,1,1,1,6;②1,1,1,1,1,2,5;③1,1,1,1,1,3,4;④1,1,1,1,2,2,4;⑤1,1,1,1,2,3,3;⑥1,1,1,2,2,2,3;⑦1,1,2,2,2,2,2.在以上7种方案中，①、②、③、⑦各有1棵非同构的树分别如图7-10(a)(b)(c)(g)，④、⑤各有2棵非同构的树分别如图7-10(d)(e)，而⑥有3棵非同构的树如图7-10(f)，共有11棵7阶非同构的树。例如④有唯一的4度顶点必须与2度顶点相邻。它与一个2度顶点相邻，所得树是非同构的，再没有其他情况，因而有2棵非同构的树。图7-102分析设T有x个1度顶点(即树叶),则T的顶点数n=3+2+x=5+x,T2解得x=5图7-113分析设3度顶点为x个，则阶数n=5+3+x=8+x，边数m=7+x.由握手定理2m=14+2x=5解得x=3，故n=8+3=11.4分析设T中有x个3度顶点，则T中的顶点数n=7+x,边数由握手定理得方程2m=12+2x解得x=5,即T中有5个3度顶点.T的度数序列为1,1,1,1,1,1,1,3,3,3,3,3.由于T中只有树叶和3度顶点，因而3度顶点可依次相邻，如图7-12所示。还有一棵与它非同构白树，请读者自己画出。图7-125分析n阶无向树T有n-1条边，这是无向树T的必要条件，但不是充分条件。例如，n-1个顶点的初级回路和一个孤立点组成的n阶无向简单图有n-1条边，但它显然不是树。即不一定。6分析当∆(T)=2时，即T的度数列为1,1,2,2,⋯,2,2的情况，此时T是一条长度为n-1的路径，故T7分析图7-1中有5个结点，因此要选取4条边。期过程如图7-13(a)-(d)所示，W(T)=22图7-138分析图7-2中有6个结点，因此要选取5条边。其过程如图7-14(a)-(e)所示，W(T)=17图7-149分析图7-3是5阶图，5阶非同构的无向树只有3棵，理由如下：5阶无向树中，顶点数n=5,边数m=4,各顶点度数之和为8,度数分配方案有3种，分别如下：①1.1.1,1,4;②1,1,1,2,3;③1,1,2,2,2。每种方案只有一棵非同构的树.图7-9中顶点的最大度数是3,所以不可能有度数序列为①的生成树.于是，该图最多有两棵非同构的生成树。在图7-9中是它的两个非同构的生成树，其中图7-9(b)的度数序列为③,图7-9(c)的度数序列为②.9.分析图7-4(a)(1)c、d、g、h为弦，它们对应的基本回路为Cc=cab，Cd=dabf，Cg(2)a、b、e、f为树枝，它们对应的基本割集系统为Sa=a,c,d,g,h,Sb=b,c,d,g,h图7-4(b)(1)g、c、d、h、i为弦，它们对应的基本回路Cg=gfe,CcCh=hjaeb,Ci(2)a、b、e、f、j为树枝.它们对应的基本割集为Sa=a,d,h,i,Sb=10分析用Kruskal算法求解，求出的图7-5(a)的最小生成树T如图7-15(a)所示，其权W(T)=14。图7-5(b)的最小生成树如图7-15(b)所示，其权W(T)=11。图7-1511分析8421码是等长码，每个数字的代码长为4，因此在译码时把编码划分为小段，每段4位，对应一个十进制数字。例如，把0101000110000111划分成0101,0001,1000,0111，分别对应5,1,8,7，故原文是5187.(1)据上可推算出7201的编码是0111001000000001,1509的编码是0001010100001001.(2)0101000110000111的原文是5187,0011010100100100的原文是3524.12分析在C1、C2、C4中任何符号串都不是另外符号串的前缀，因而他们都是前缀码.而在C3中，1是11、101的前缀.在C5中，a是aa、ac13分析一般地，由r叉树产生r元前缀码。由图7-4(a)给出的二元前缀码为C由图7-4(b)给出的二元前缀码为C214分析然后继续往下.如11001010100、1、11和110都不是代码，1100是4的代码，译出4.继续往下，1和10都不是代码，101是3的代码，译出3.再往下，01、00分别是1、0的代码.于是，它的原文是4310.(2)6014的编码是111000011100,1725的编码是0111111001101.(3)11001010100代表的八进制数是4310,01111100100代表的八进制数是1702.15分析将所有的频率都乘100，所得结果按从小到大顺序排序：wg=5，wf=5，wc=15，w以上各数为权，用Huffman算法求一课最优二叉树，图7-16所示。图7-16对照各个权可知各字母的前缀码如下：a-10，b-01，c=111，d-110，e-001，f-0001，g于是，a、b的码长为2，c、d、e的码长为3，f、g的码长为4.W(T)=255（各分支点的权之和），W(T)是传输100个按给定频率出现的字母所用的二进制数字的个数，因而传输104个按上述频率出现的字母要用2.55最后还应指出一点，在画最优树时，由于顶点位置的不同，可能得到不同的前缀码.事实上，交换相同码长的代码和交换频率相同的字母的代码不会改变需要的二进制数字的期望个数.从而，只要它们中有一个是最佳前缀码，其他的也都是最佳前缀码.分析(1)用中序遍历法访问该树，得到(((a省去一些圆括号，得到算式的表达式((a(2)用前序遍历法访问这棵树并删去所有的圆括号，得到算式的波兰符号法表达式+*÷-*abc+d*ef(3)用后序遍历法访问这棵树并删去所有的圆括号，得到算式的逆波兰符号法表达式ab*c-def*+÷提升习题1分析(1)用中序行遍法访问这棵树，得到(((a+(b*c))*d-e)省去一些圆括号，得到算式的表达式((a+(b*c))*d-e)用前序行遍法访问这棵树并删去所有的圆括号，得到算式的波兰符号法表达式+(3)用后序行遍法访问这棵树并删去所有的圆括号，得到算式的逆波兰符号法表达式abc*+d*e-fg+将变量的值代入波兰符号法表达式+计算如下：++++÷+÷++(12)在上面为了区分一位数和二位数，用括号把二位数括起来.将变量的值代入逆波兰符号法表达式431*+3*3-12+计算如下：431*43+73*(21)3-12+(18)(18)366666(12)2分析逻辑运算中有一元运算符¬，因此表示命题公式的二叉树不是正则的.由于¬的运算对象跟在它的后面，所以为了用中序行遍法访问能恢复原式，¬所在顶点的儿子应为右儿子.不过抱着对用前序行遍法访问和用后序行遍法访问的结果没有影响.表示命题公式的二叉树如图7-17所示.用前序行遍法访问该树并删去所有圆括号，得到命题公式的前缀符号法表达式→用后序行遍法访问该树并删去所有圆括号，得到命题公式的后缀符号法表达式pq图7-173分析（1）设计思路输入：赋权连通图G=<V,E>。输出：G的一个最小生成树。实现语言：C语言。基本思路：使用Prim算法。在G中任意选取一个结点v1，置VT={v1在V-VT中选取与某个vi∈VT邻接的结点vj，使得边重复（b），直到k=|V|。（2）参考代码/*Prim算法求赋权图的最小生成树*/#include<stdi.h>#defineN7//图的阶数#defineINF1000//不相邻的点，距离设为一个极大数字structedge{intstart;Intend;intweight;};//w为图的权值矩阵intw[N][N]={{0,12,INF,INF,INF,16,14},{12,0,10,INF,INF,7,INF},{INF,10,0,3,5,6,INF},{INF,INF,3,0,4,INF,INF},{INF,INF,5,4,0,2,8},{14,INF,INF,INF,8,9,0}};intverteces[N}={0};//点加入生成树的顺序,node中的点属U,不在node中的属于V-Ustructedgeedges[N];//U中顶点到V-U中顶点的最小权值的边inttree[N][N]={0};//存储最小生成树intsum=0;/*从所有的u属于U,v属于V-U(V-U表示除去U的所有顶点)的边中选取权值最小的边(u,v)，*将顶点v加入集合U中,将边(u,v)加入集合T中*/intmain(){//将权值数组初始化为“第1个顶点”到“该顶点”的权值。for(intk=0;k<N;k++){edges[k}.start=0;edges[k].end=k;edges[k].weight=w[0][k];}//第一个点加入node,此为起点vertexes[0]=1;//Primfor(intk=1;k<N;k++){intindex=0;intmin=INF;//找到权值最小的uv边,u属于U,v属于V-Ufor(intj=0;j<N;j++){if(edges[j].weight!=0&&edges[j].weight<min){min=edges[j].weight;index=j;}}if(min==INF){printf(“图G没有最小生成树！\n”);return0;}elsesum+=min;//顶点(index+1)加入nodes,到该顶点的权值置0vertexes[k]=index+1;tree[edges[index].start][edges[index].end]=edges[index].weight;tree[edges[index].end][edges[index].start]=edges[index].weight;edges[index].weight=0’//更新weightsfor(intj=0;j<N;j++){//当第j个节点没有在树中，并且有权值更小的边时才被更新if(edges[j].weight!=0&&w[index][j]<edges[j].weight){edges[j