第七章---图

第七章图7.1解：(1)ID(1)=3OD(1)=0ID(2)=2OD(2)=2ID(3)=1OD(3)=2ID(4)=1OD(4)=3ID(5)=2OD(5)=1ID(6)=2OD(6)=3(2)000000100100010001001011100000110010(3)(4)(5)有三个连通分量1、5、23467.7请对下面的无向带权图，（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁期卡尔算法求其最小生成树。解：（1）图的邻接矩阵为7.9试列出题7.9图中全部可能的拓扑有序序列,并指出应用7.5.1节中算法TopologicalSort求得的是哪一个序列（注意：应先确定其存储结构）。StatusTopologicalSort(ALGraphG)FindIndegree(G,indegree);//对各顶点求入度InitStack(S);For(i=0;iG.vexnum;i++)//建0入度顶点栈SIf(!Indegree[i])Push(S,i);//入度为0者进栈count=0;//对输出顶点计数while(!StackEmpty(s)){Pop(S，i);printf(i,G.vertices[i].data);++count;//输出i号顶点并计数for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;//对i号顶点的每个邻接点的入度减1if（!(--indegree[k])）Push(S,k);//入度减为0，则入栈}}if（countG.vexnum）returnERROR;//该有向图有回路elsereturnOK;}求得5612347.11试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径,写出执行算法过程中各步的状态。7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。解：intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS7.23③同7.22题要求。试基于图的广度优先搜索策略写一算法。解：intexist_path_BFS(ALGraphG,inti,intj)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{intvisited[MAXSIZE];InitQueue(Q);EnQueue(Q,i);while(!QueueEmpty(Q)){DeQueue(Q,u);visited[u]=1;for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;if(k==j)return1;if(!visited[k])EnQueue(Q,k);}//for}//whilereturn0;}//exist_path_BFS第9章查找9.2试分别画出在线性表（a,b,c,d,e,f,g）中进行折半查找，以查关键字等于e,f和g的过程。解：1）查找e的过程如下：2)查找f的过程3）查找g的过程9.3画出对长度为10的有续表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。解：9.243342211101ASL9.9已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）(1)试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。解：（1）求得的二叉排序树如下图所示：JanFebMarAprAugDecJuneJulyMaySeptOctNov在等概率情况下查找成功的平均查找长度为：ASL成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5(2)分析：对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。所以可求出：ASL成功=（1+2*2+4*3+5*4）/12=37/12（3）平衡二叉树的构造过程平衡二叉树为9.21在地址空间为0~16的散列区中，对以下关键字序列构造两哈希表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）(1)用线性探测开放定址法处理冲突；(2)用链地址法处理。并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希函数为H(x)=i/2取整,其中i为关键字中第一个字母在字母表中的序号。解：（1）因为：H(Jan)=5;H(Feb)=3;H(Mar)=6;H(Apr)=0;H(May)=6;H1(May)=7;H(June)=5;H1(June)=6;H2(June)=7;H3(June)=8H(July)=5;H1(July)=6;H2(July)=7;H3(July)=8;H4(July)=9;H(Aug)=0;H1(Aug)=1H(Sep)=9;H1(Sep)=10H(Oct)=7;H1(Oct)=8;H2(Oct)=9;H3(Oct)=10;H4(Oct)=11;H(Nov)=7;H1(Nov)=8;H2(Nov)=9;H3(Nov)=10;H4(Nov)=11;H5(Nov)=12;H(Dec)=2所以，用线性探测开放定址法处理冲突构造的哈希表如下图所示：012345678910111213141516AprAugDecFebJanMarMayJuneJulySepOctNovCi:121111245256并求得：ASL成功=（1*5+2*3+4+5*2+6）/12=31/12ASL不成功=（5+4+3+2+1+9+8+7+6+5+4+3+2+1）/14=60/14（2）用链地址法处理冲突构造的哈希表如下图所示：^^^^^0123456789101112131415AprAug^Dec^Feb^JanJulyJune^MarMay^NovOct^Sep^^^^^^并求得：ASL成功=（1*7+2*4+3）/12=18/12ASL不成功=（1*3+2*3+3）/14=12/149.25假设顺序表按关键字自大至小有序，试改写教科书9.1.1节中的顺序查找算法，将监视哨设在高下标端。然后画出描述此查找过程的判定树，分别求出等概率下查找成功和不成功的平均查找长度。解：（1）顺序表的存储结构描述：Typedefstruct{Keytypekey;}Elemtype;//记录类型；typedefstruct{Elemtype*elem;intlength;}SSTable;//顺序表类型；按要求所得算法如下：intSearch(SSTableST,Keytypekey){ST.elem[ST.length].key=key;for(i=0;keyST.elem[i].key;i++);if(i==ST.length)return0;elseif(key==ST.elem[i].key)returni;elsereturn0;}(2)按此查找过程的判定树如下图所示：123n（3）等概率下的查找成功与查找不成功的平均查找长度分别为：、ASL成功=（1+2+3+….+n）/n=(n+1)/2ALS不成功=（2+3+…+n+(n+1)）/n=(n+2)/29.26试将折半查找的算法改成递归算法。intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法{if(lowhigh)return0;//查找不到时返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].keykey)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive9.32已知一棵二叉排序树上所有关键字中的最小值为-max，最大值为max，又-maxxmax。编写具有如下功能的函数：求该二叉树上小于x且最靠近x的值a和大于x且最靠近x的b。intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{if(T-lchild)MaxLT_MinGT(T-lchild,x);//本算法仍是借助中序遍历来实现if(lastx&&T-data=x)//找到了小于x的最大元素printf(a=%d\n,last);if(last=x&&T-datax)//找到了大于x的最小元素printf(b=%d\n,T-data);last=T-data;if(T-rchild)MaxLT_MinGT(T-rchild,x);}//MaxLT_MinGT