数据结构与算法习题讲解(全)解析

第一章1.5编写一个递归方法，它返回数n的二进制表示中1的个数。利用这样的事实：如果n是奇数，那么它等于n/2的二进制表示中1的个数加1。①intones(intn){if(n<2)returnn;returnn%2+ones(n/2);}数据结构与算法习题讲解(全)解析全文共97页，当前为第1页。②#include<iostream.h>usingnamespacestd;intj=0;count(intn){intk;k=n/2;j++;while(k>=1){if(n%2==0)j--;returncount();}}main(){inti,j;cout<<“Pleaseinputn:”<<endl;cin>>i;if(i<0)i=-i;count(i);cout<<“所输入整数中的二进制中1的个数是：”<<j<<endl;return0;}数据结构与算法习题讲解(全)解析全文共97页，当前为第2页。1.7证明下列公式a.logx<x对所有的x>0成立①数学归纳法：当0<x≤1,命题显然成立：x=1,公式是成立的；当x<1时,logx是负数。同理可以很容易推出当1<x≤2时命题成立：x=2,公式成立；当x<2,logx最大为1。假设命题在p<x≤2p时成立(p为正整数),这时考虑有2p<Y≤4p(p≥1)。则logy=1+log(y/2)<1+y/2<y/2+y/2≤y,由此可推导出公式成立。数据结构与算法习题讲解(全)解析全文共97页，当前为第3页。②二项式法：令x=2x,有log2x<2x,即x<2x

又2x=(1+1)x=C0x+C1x+…+Cxx=1+x+C2x+…+x+1>x

即2x>x,得logx<x;命题得证b.log(AB)=BlogA证明：令2X=A,则AB=(2X)B=2XB;

则logAB=XB,X=logA;命题得证数据结构与算法习题讲解(全)解析全文共97页，当前为第4页。第二章2.1按增长率排列函数：N,N1/2,N1.5,N2,NlogN,Nlog(logN),Nlog2N,Nlog(N2),2/N,2N,2N/2,37,N2logN,N3。指出哪些函数以相同的增长率增长。答：2/N,37,N1/2,N,Nlog(logN),NlogN,Nlog(N2),Nlog2N,N1.5,N2,N2logN,N3,2N/2,2N.

其中，NlogN,Nlog(N2)有相同的增长率。常见的几种计算时间的关系：

O(1)<O(logN)<O(N)<O(NlogN)<O(N2)<O(N3)O(2N)<O(N!)<O(NN)数据结构与算法习题讲解(全)解析全文共97页，当前为第5页。2.7对于下列六个程序片段中的每一个：给出运行时间分析1)sum=0;2)sum=0;for(i=0;i<n;i++)for(i=0;i<n;i++)sum++;for(j=0;j<n;j++)O(N)sum++;O(N2)数据结构与算法习题讲解(全)解析全文共97页，当前为第6页。3)sum=0;for(i=0;i<n;i++)for(j=0;j<n*n;j++)sum++;O(N3)4)sum=0;for(i=0;i<n;i++)for(j=0;j<i;j++)sum++;O(N2)数据结构与算法习题讲解(全)解析全文共97页，当前为第7页。5)sum=0;for(i=0;i<n;i++)for(j=0;j<i*i;j++)for(k=0;k<j;k++)sum++;O(N5)j可等规模于i2,同样也等规模于N2.k等规模于j,即N2.则该程序段的运行时间复杂度分析为N*N2*N2,即O(N5).

数据结构与算法习题讲解(全)解析全文共97页，当前为第8页。6)sum=0;for(i=1;i<n;i++)for(j=1;j<i×i;j++)*if(j%i==0)for(k=0;k<j;k++)sum++;O(N4)注：*处的for语句的循环次数为“12+22+32+…+n2”,如上题所述if语句至多要执行N3次,但是实际上只有O(N2)次(因为对每一个i，实际上都严格执行了i次),因此最内的循环只执行了O(N2)次。而每执行一次,将花费O(j2)

=O(N2)

的时间,总数即为O(N4)。个人理解：

if(j%i==0)for(k=0;k<j;k++)sum++;这段程序段的循环次数O(N)数据结构与算法习题讲解(全)解析全文共97页，当前为第9页。2.8假设需要生成n个自然数的一个随机置换。例如：{4,3,1,5,2}和{3,1,4,2,5}就是合法的置换，但{5,4,1,2,1}则不是，因为数1出现2次而数3却没有。这种程序常常用于模拟一些算法。我们假设存在一个随机数生成器n，它用方法randInt(i,j)以相同的概率生成i和j之间的一个整数。下面是三个算法：

(1).如下填入从a[0]到a[n-1]的数组a:为了填入a[i],生成随机数直到它不同于已经生成的一个a[0],a[1],…,a[i-1]时再将其填入；

(2).同算法(1)，但是要使用一个附加的数组，称之为used数组。当一个随机数ran最初被放入数组a的时候，设置used[ran]=ture。就是说，当一个随机数填入a[i]时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样可能用i步来测试；

(3).填写该数组，使得a[i]=i+1，然后for(i=1;i<n;i++)swap(a[i],a[randInt(0,i)]);试问：

a.证明这三个算法都生成合法的置换，并且所以的置换都是等可能的；

b.对每个算法都给出你能够得出的尽可能不同的期望运行时间分析；

c.没个算法的最坏情形的运行时间是什么？数据结构与算法习题讲解(全)解析全文共97页，当前为第10页。答：a.所有的算法都可以生成合法的置换。很明显，前2个算法在测试中可以保证不生成重复的数，并且它们是完全随机的，故它们生成的置换是等可能。第3个算法轮换数组中的元素，这个数组最初是没有重复数的，也不会存在非法置换。前2个算法很明显成立，第3个算法可以用数学归纳法证明，详细证明如下：数据结构与算法习题讲解(全)解析全文共97页，当前为第11页。1.当n=1时，a[0]=1，都是100%，成立；2.当n=2时，for(i=1;i<n;++i)swap(a[i],a[randInt(0,i)]);

第一次循环，当i=1时，即a[0]=1,a[i]=a[1]；3.当n=3时，第二次循环时，当i=2时，此时有两种可能，原序列为0,1;1,0的几率各为50%。randInt(0,2)可能为0,1,2的几率各为1/3。此时,原序列为0,1时,randInt(0,2)为0,那么此序列经过swap(a[2],a[0]),最后序列为2,1,0,此序列的可能性为(1/2)*(1/3)=1/6;同理易得,最后此序列为“210,021,012,201,120,102”的几率各为1/6,而此序列的所有排列可能为=3*2=6,所以，此时成立。4.假设此命题在n=k时成立，那么就是说，ｋ前面序列共有序列k-1种，且所有序列的几率为1/((k-1)*k)。5.当n=k+1时,第k+1次循环时,前面序列正好为n=k时的情况,此时i=k.randInt(0,k)共可能为0~k,k+1种可能。所以以前的每个可能序列在置换后有k+1种可能，而以前共有k种等可能序列，那么最后可能的序列为k*(k+1)种可能，并且，因为原序列为等可能的，每个等可能序列产生的序列都是k+1种，所以最后的序列也是等可能的。而当n=k+1时，应该共有=(k+1)*k种，所以，此命题得证。数据结构与算法习题讲解(全)解析全文共97页，当前为第12页。注：证明时默认地利用了一个命题：当原序列为互不相等的等可能序列时，新加入一个与原来序列任何数值都不相等的数值，无论这个数值放在原序列的哪个位置，都不可能使原不相等的序列相等。例：210,021,012,201,120,102，这时加入一个新的数值3，无论把3插入序列的哪个位置，因为原来序列的排列不相等，所以，他们还是不会相等，这样，才保证了最后k个序列的k+1种可能都不相等，不会重复。数据结构与算法习题讲解(全)解析全文共97页，当前为第13页。b.第一个算法中，决定a[i]中一个之前没有使用过的随机数是否被填入的时间是O(i)。在那些需要测试的随机数中，需要产生期望的随机数的次数为N/(N−i)次。得出结论如下：n个数中有i个可能是重复的。因此，置换成功的概率为(N−i)/N。因此，在独立的测试中，期望数为N/(N−i)。时间复杂度即为：数据结构与算法习题讲解(全)解析全文共97页，当前为第14页。第2个算法为每个随机数保留了因子i，因此，时间度平均减少到了O(NlogN)

。第3个算法很明显是线性的，O(N)。数据结构与算法习题讲解(全)解析全文共97页，当前为第15页。c.算法1和算法2的最坏运行时间无法被界定，在一直随机到重复数字的时候可以到达无限大。算法3的运行时间是线性的——它的运行时间并不依赖于随机数的次序。数据结构与算法习题讲解(全)解析全文共97页，当前为第16页。2.12一个算法对于大小为100的输入花费0.5ms，如果运行时间如下：则用1min可以解决多大的问题(设低阶项可以忽略)。

a.是线性的；b.为O(NlogN)c.是二次的；d.是三次的数据结构与算法习题讲解(全)解析全文共97页，当前为第17页。(a)12000timesaslargeaproblem,orinputsize1,200,000.N=60*1000*100/0.5=12,000,000=1.2*107(b)inputsizeofapproximately425,000.

由NlogN=1.2*107

可得(c)120001/2timesaslargeaproblem,orinputsize10,954.

由N2=1.2*107

可得(d)120001/3timesaslargeaproblem,orinputsize2,289.

由N3=1.2*107可得数据结构与算法习题讲解(全)解析全文共97页，当前为第18页。2.18数值分析中一个重要的问题是对某一个任意的函数f找出方程f(x)=0的一个解。如果该函数是连续的，并有两个点low和hign使得f(low)和f(high)符号相反，那么在low与high之间必然存在一个根。并且这个根可以通过二分搜索求得。写一个函数，以f,low和high为参数，并且解出一个零点。数据结构与算法习题讲解(全)解析全文共97页，当前为第19页。floatfind(floatlow,floathigh){mid=(low+high)/2;if(fabs(f(mid))<=0.000001)

returnmid;elseif(f(mid)*f(low)<0)find(low,mid);elsefind(mid,high);}为使程序正常终止，必须设置基准情况。（注意精度防止溢出）数据结构与算法习题讲解(全)解析全文共97页，当前为第20页。一个例子：#include<stdio.h>#include<math.h>floatf(floata){return5*a+1;}voidfind(float,float);floatstaticc=0;voidmain(){

find(-4,5.0); printf("%f\n",c); return0;}voidfind(floatlow,floathigh){

floatmid=(low+high)/2; if(fabs(f(mid))<=0.0001) { c=mid; } else { if(f(mid)*f(low)<0) find(low,mid); else find(mid,high); }}数据结构与算法习题讲解(全)解析全文共97页，当前为第21页。2.26大小为N的数组A，其主元素是一个出现超过N/2次的元素(从而这样的元素最多有一个)。例如：数组：3,3,4,2,4,4,2,4,4有一个主元素4；而数组3,3,4,2,4,4,2,4没有主元素。如果没有主元素，那么你的程序应该指出来。a.递归如何终止？

b.当N是奇数时的情形如何处理？

c.该算法的运行时间是多少？

d.我们如何避免使用附加数组B？数据结构与算法习题讲解(全)解析全文共97页，当前为第22页。a.如果只有2个或更少的元素，不需要递归。

b.一种方法是：标记，如果前N-1个元素已经出现主元素，则最后一个元素不需要考虑。否则，最后一个元素有可能是主元素。因此当N是奇数时，忽略最后一个元素。像之前一样运行算法。如果没有主元素出现，则将第N个元素作为候选值返回。c.运行时间为O(N),并且满足T(N)=T(N/2)+O(N)。d.保存一份数据到数组B。之后，通过复制每一个Bi到数组A即可避免递归。区别在于原递归策略将要用到O(logN)个数组，现在只需要用2个。数据结构与算法习题讲解(全)解析全文共97页，当前为第23页。第三章链表、堆栈、队列3.2通过只调整链而不是数据来交换两个相邻的元素使用。a.单向链表b.双向链表数据结构与算法习题讲解(全)解析全文共97页，当前为第24页。(a)singlelinkedlists://beforepisthecellbeforethetwoadjacentcellsthataretobe//swapped//ErrorchecksareomittedforclarityvoidswapWithNext(Node*beforep){Node*p,*afterp;p=beforep->next;afterp=p->next;//bothpandafterpassumednotNULLp->next=afterp->next;beforep->next=afterp;afterp->next=p;}beforepnextpnextafterpnext数据结构与算法习题讲解(全)解析全文共97页，当前为第25页。(b)doublylinkedlists://pandafterparecellstobeswitched.Errorchecksasbefore{Node*beforep,*afterp;beforep=p->prev;afterp=p->next;p->next=afterp->next;beforep->next=afterp;afterp->next=p;p->next->prev=p;p->prev=afterp;afterp->prev=beforep;}beforepprevnextpprevnextafterpprevnext数据结构与算法习题讲解(全)解析全文共97页，当前为第26页。3.6Josephus问题是下面一个游戏：有N个人坐成一圈，编号为1至N。从编号为1的人开始传递热马铃薯。M次传递之后，持有马铃薯的人退出游戏，圈缩小，然后游戏从退出的下面的人开始继续，最终留下的获胜。这样M=0且N=5，那么参加游戏的人依次退出，5号获胜。a.写出一个程序来解决Josephus问题，此时M和N为任意值，尽可能使程序高效，同时确保存储单元被正确处理。b.程序运行时间是多少？c.当M=1时，程序运行时间是多少？对于N的较大值（N>100000），delete例程对程序运行速度的影响有多大？数据结构与算法习题讲解(全)解析全文共97页，当前为第27页。分析：Thisisastandardprogrammingproject.ThealgorithmcanbespedupbysettingM’=MmodN,sothatthehotpotatonevergoesaroundthecirclemorethanonce.IfM>N/2,thepotatoshouldbepassedinthereversedirection.Thisrequiresadoublylinkedlist.TheworstcaserunningtimeisclearlyO(Nmin(M,N)),althoughwhentheheuristicsareused,andMandNarecomparable,thealgorithmmightbesignificantlyfaster.IfM=1,thealgorithmisclearlylinear.数据结构与算法习题讲解(全)解析全文共97页，当前为第28页。解（1）：#include<iostream>#include<list>usingnamespacestd;intmain(){inti,j,n,m,mPrime,numLeft;list<int>L;list<int>::iteratoriter;//Initializationcout<<"enterN(#ofpeople)&M(#ofpassesbeforeelimination):";cin>>n>>m;numLeft=n;mPrime=m%n;for(I=1;I<=n;i++)L.push_back(i);iter=L.begin();//Passthepotatofor(I=0;I<n;i++){mPrime=mPrime%numLeft;if(mPrime<=numLeft/2)//passforwardfor(j=0;j<mPrime;j++){iter++;if(iter==L.end())iter=L.begin();}else//passbackwardfor(j=0;j<mPrime;j++){if(iter==L.begin())iter=--L.end();elseiter--;}cout<<*iter<<"";iter=L.erase(iter);if(iter==L.end())iter=L.begin();}cout<<endl;return0;}数据结构与算法习题讲解(全)解析全文共97页，当前为第29页。解（2）：voidfindout(intn,intm){intbuf[max];intdex=0;intin=0;for(inti=1;i<=n;i++)//n是人数

{buf[i]=i;//给n个人赋号码}while(n>in+1)//剩下人数大于1的时候才执行

{for(i=1;i<=n;i++)//遍历所有人

{if(buf[i]!=0)//个人号码不为0的时候

{dex++;if(dex==m)//若是数到m,{buf[i]=0;//则把此人的号码改成0in++;//出圈人的个数加1dex=0;//判断值清0,从新开始找

}}}}//while退出的时候只剩下一个人

for(i=1;i<=n;i++)if(buf[i]!=0)printf(“最后获胜者号码为:%d\n",buf[i]);}数据结构与算法习题讲解(全)解析全文共97页，当前为第30页。3.20不同于我们已经给出的删除方法，另一种是使用懒惰删除的方法。为删除一个元素，我们只是标记元素被删除表中被删除和未被删除元素的个数作为数据结构的一部分被保留。如果被删除元素和未被删除元素一样多，则遍历整个表，对所有被标记的结点执行标准的删除算法。a.列出懒惰删除的优点和缺点b.写出使用懒惰删除实现标准链表操作的例程。数据结构与算法习题讲解(全)解析全文共97页，当前为第31页。(a)

优点在于：编码简单，并且如果被删除的键在之后被重新插入（在同一位置），可以节省资源。缺点在于：需要更多的空间；因为每一个单元都需要额外的位（典型的如1byte）,且未使用的单元空间并没有被释放。(b)略数据结构与算法习题讲解(全)解析全文共97页，当前为第32页。3.28双端队列是由某些项的一个表组成的数据结构，对该数据结构可以进行下列操作：push(x):将项x插入双端队列的前端pop(x):从双端队列中删除前端项并将其返回infect(x):将项x插入到双端队列的尾端eject():从双端队列中删除尾端项并将其返回编写支持双端队列的例程，每种操作均花费O(1)时间。数据结构与算法习题讲解(全)解析全文共97页，当前为第33页。需要使用双向链表，其上有指向头结点和尾结点的指针。实际上可通过重命名链表的操作符，用一个链表实现。

template<typenameObject>classdeque{public:deque(){l();}voidpush(Objectobj){l.push_front(obj);}Objectpop();{Objectobj=l.front();l.pop_front();returnobj;}voidinject(Objectobj);{l.push_back(obj);}Objecteject();{pop_back(obj);}private:list<Object>l;};数据结构与算法习题讲解(全)解析全文共97页，当前为第34页。3.35实现队列的一种方法是使用一个循环链表，在循环链表中，最后一个结点的next指针指向第一个结点。假设该表不包括表头，而且我们最多可保留一个迭代器，它对应表中的一个结点。对于下列的哪种表示，所有基本队列操作可以以常数最坏情况时间执行？证明你的答案是正确的。a.保留一个迭代器，它对应该表的第一项b.保留一个迭代器，它对应该表的最后一项数据结构与算法习题讲解(全)解析全文共97页，当前为第35页。注：队列是FIFO的(a)

在尾结点插入时，不能以常数时间执行。(b)

因为是循环链表,我们可以以常数时间访问链表前端,因此b情况可以。数据结构与算法习题讲解(全)解析全文共97页，当前为第36页。第四章树4.2对于图中树上的结点（每一个），a.指出它的父结点b.列出它的儿子、兄弟c.算出它的深度高度ABCDFEJGHKILM数据结构与算法习题讲解(全)解析全文共97页，当前为第37页。解：对任意一个结点M，有五元组M{father;Sibling[];Brother[];depth;height},则有：A{NULL;B,C;NULL;0;4}H{D;NULL;G;3;0}B{A;D,E;C;1;3}I{E;NULL;J;3;0}C{A;F;B;1;2}J{E;L,M;I;3;1}D{B;G,H;E;2;1}K{F;NULL;NULL;3;0}E{B;I,J;D;2;2}L{J;NULL;M;4;0}F{C;K;NULL;2;1}M{J;NULL;L;4;0}G{D;NULL;H;3;0}数据结构与算法习题讲解(全)解析全文共97页，当前为第38页。4.8给出对应图中的树的前缀表达式，中缀表达式以及后缀表达式。解：前缀表达式：-**ab+cde中缀表达式：((a*b)*(c+d))-e后缀表达式：ab*cd+*e--*e*+dabc数据结构与算法习题讲解(全)解析全文共97页，当前为第39页。4.9题：a.指出将[3，1，4，6，9，2，5，7]插入到初始为空的二叉查找树中的结果b.指出删除根后的结果解：314297565416279数据结构与算法习题讲解(全)解析全文共97页，当前为第40页。4.27指出依序访问图中伸展树键3，9，1，5后的结果10111312462135879数据结构与算法习题讲解(全)解析全文共97页，当前为第41页。解：Afteraccessing3,（第一次旋转后，呈“一字形”）31210111213468579数据结构与算法习题讲解(全)解析全文共97页，当前为第42页。Afteraccessing9,（经旋转后，最后一次呈“之字形展开”）31210111213468579数据结构与算法习题讲解(全)解析全文共97页，当前为第43页。Afteraccessing1,（“一字形”）16857101112139324数据结构与算法习题讲解(全)解析全文共97页，当前为第44页。Afteraccessing5,（“一字形”……“之字形”）18571011121393246数据结构与算法习题讲解(全)解析全文共97页，当前为第45页。4.43指出如何用儿子/兄弟链实现方法表示图中的树ABGJKLCNFDEIHMOPQR数据结构与算法习题讲解(全)解析全文共97页，当前为第46页。ABDHEIJCFKLOMPQRGN解：数据结构与算法习题讲解(全)解析全文共97页，当前为第47页。6.2题：a.写出一个一次将10，12，1，14，6，5，8，15，3，9，7，4，11，13和2插入到一个初始为空的二叉堆中的结果b.写出使用相同的输入通过线性时间算法建立一个二叉堆的结果。第六章优先队列（堆）数据结构与算法习题讲解(全)解析全文共97页，当前为第48页。解：（1）堆排序；（2）下滤132675415141291011138132126481514975111310数据结构与算法习题讲解(全)解析全文共97页，当前为第49页。6.3写出对上面练习中的堆执行3次deletMin操作后的结果：解：465127108151491311465137108151412911数据结构与算法习题讲解(全)解析全文共97页，当前为第50页。6.15设一个d堆初始化时有N个元素，而我们需要对其执行M次percolateUp(上滤)和N次deleteMin（删除最小元）。a.用M、N和d表示的所有操作的总运行时间是多少：b.如果d=2，所有的堆操作的运行时间是多少？c.如果d=O(N)，总的运行时间是多少？*d.怎样选择d将使总的运行时间最小？数据结构与算法习题讲解(全)解析全文共97页，当前为第51页。(a)O((M+dN)logdN).(b)O((M+N)logN).(c)O(M+N2).(d)d=max(2,M/N).数据结构与算法习题讲解(全)解析全文共97页，当前为第52页。6.19合并图中的两个左式堆21112171858154961018311121数据结构与算法习题讲解(全)解析全文共97页，当前为第53页。解：24951018318156112111121718数据结构与算法习题讲解(全)解析全文共97页，当前为第54页。6.27写出将键1到15依次插入到一斜堆内的结果。解：132756415111391410128数据结构与算法习题讲解(全)解析全文共97页，当前为第55页。6.32将图中的两个二项队列合并。13235124651221246514161826415182552911数据结构与算法习题讲解(全)解析全文共97页，当前为第56页。解：25529114181513235124651221246514261618数据结构与算法习题讲解(全)解析全文共97页，当前为第57页。第七章排序7.1使用插入排序将序列3,1,4,1,5,9,2,6,5排序。Original3,1,4,1,5,9,2,6,5Afterp=2Afterp=3Afterp=4Afterp=5Afterp=6Afterp=7Afterp=8Afterp=91,3,4,1,5,9,2,6,51,3,4,1,5,9,2,6,51,1,3,4,5,9,2,6,51,1,3,4,5,9,2,6,51,1,3,4,5,9,2,6,51,1,2,3,4,5,9,6,51,1,2,3,4,5,6,9,51,1,2,3,4,5,5,6,9数据结构与算法习题讲解(全)解析全文共97页，当前为第58页。7.4写出使用增量{1,3,7}对输入数据9,8,7,6,5,4,3,2,1运行希尔排序得到的结果。Original9,8,7,6,5,4,3,2,1After7-sortAfter3-sortAfter1-sort2,1,7,6,5,4,3,9,82,1,4,3,5,7,6,9,81,2,3,4,5,6,7,8,9数据结构与算法习题讲解(全)解析全文共97页，当前为第59页。7.11指出堆排序如何处理输入数据142,543,123,65,453,879,572,434,111,242,811,102。解：输入数据为：142,543,123,65,453,879,572,434,111,242,811,102堆化后输出的结果为：879,811,572,434,543,123,142,65,111,242,453,102把堆顶元素879输出并置于堆的末尾。这里用斜体表示以说明它已不是堆的一部分。将102替代原堆顶的位置并进行比较调整后，得:811,543,572,434,453,123,142,65,111,242,102,879数据结构与算法习题讲解(全)解析全文共97页，当前为第60页。反复进行上述过程，可得：572,543,142,434,453,123,102,65,111,242,811,879543,453,142,434,242,123,102,65,111,572,811,879453,434,142,111,242,123,102,65,543,572,811,879434,242,142,111,65,123,102,453,543,572,811,879242,111,142,102,65,123,434,453,543,572,811,879142,111,123,102,65,242,434,453,543,572,811,879123,111,65,102,142,242,434,453,543,572,811,879111,102,65,123,142,242,434,453,543,572,811,879102,65,111,123,142,242,434,453,543,572,811,87965,102,111,123,142,242,434,453,543,572,811,879数据结构与算法习题讲解(全)解析全文共97页，当前为第61页。7.15用归并排序将3,1,4,1,5,9,2,6排序解：首先设前半部分序列{3,1,4,1}是已排序的。对其,设序列{3,1}是已排序的。该序列包含了序列基准情形{3}和{1},则可通过归并结果得到{1,3}。序列{4,1}可同样地排序为{1,4}。这样即可将两序列归并得到{1,1,3,4}。相应的设后半部分序列是已排序的，用类似的排序方法,可逐步得到序列{2,5,6,9}.最终再将两部分序列用归并算法合并到一起，易得{1,1,2,3,4,5,6,9}。归并算法则是一种经典的分治策略数据结构与算法习题讲解(全)解析全文共97页，当前为第62页。7.19用三数中值分割法以及截止为3的快速排序将3,1,4,1,5,9,2,6,5,3,5排序。解：原输入为：3,1,4,1,5,9,2,6,5,3,5对左段、中间位置和右端元素进行排序后，得到：3,1,4,1,5,5,2,6,5,3,9因此，枢纽元为5，交换使枢纽元离开得到：3,1,4,1,5,3,2,6,5,5,9数据结构与算法习题讲解(全)解析全文共97页，当前为第63页。第一次交换在两个5之间进行。第二次交换时i和交错j，此时枢纽元与i进行交换得:3,1,4,1,5,3,2,5,5,6,9对前8个元素递归地进行快速排序:3,1,4,1,5,3,2,5对三数进行排序得:1,1,4,3,5,3,2,5则得到枢纽元为3,交换后得:1,1,4,2,5,3,3,5第一次交换在4和3之间:1,1,3,2,5,4,3,5下一次交换时i和j已经交错，故不再交换。此时i指向5，则枢纽元与其交换得:1,1,3,2,3,4,5,5数据结构与算法习题讲解(全)解析全文共97页，当前为第64页。调用递归对上述序列的前4个元素进行排序，得其枢纽元为1,且分割段没有改变。因子序列低于截止,故不进行操作。类似的，最后3个元素构成了一个基准情形,不进行操作。现在加入后面的3个元素，对右边子序列进行快速排序，因其只有3个元素，故不进行操作。得到：1,1,3,2,3,4,5,5,5,6,9其中，对截止范围内的小数组进行了插入排序。数据结构与算法习题讲解(全)解析全文共97页，当前为第65页。7.28当实现快速排序时，如果数组包含许多重复元，那么可能更好的方法是执行3路划分(划分成小于、等于以及大于枢纽元的三部分元素)以进行更小的递归调用。假设有如compareTo方法提供的3路比较。a)给出一个算法，该算法只使用N-1次3路比较而将一个N元素子数组实施3路原位划分。如果有d项等于枢纽元，那么可以使用d次附加的Comparable交换，高于和超越2路分割算法(提示：随着i和j彼此相向移动，保持5组元素如下)：EQUALSMALLUNKNOWNLARGEEQUALijb)证明，使用上面的算法将只含有d个不同值的N元素数组排序花费O(dN)时间。（详解略）参见J.L.BentleyandM.D.McElroy,“EngineeringaSortFunction,”Software—PracticeandExperience数据结构与算法习题讲解(全)解析全文共97页，当前为第66页。第九章9.1找出下图的一个拓扑排序sDEFtCBAGHI222413341321342626163数据结构与算法习题讲解(全)解析全文共97页，当前为第67页。解：下列排序是通过队列获得的，且顶点在邻接表中是以字母顺序出现的。此拓扑排序为：s,G,D,H,A,B,E,I,F,C,t数据结构与算法习题讲解(全)解析全文共97页，当前为第68页。9.5a)找出下图中A点到所有其他顶点的最短路径。b)找出下图中B点到所有其他顶点的最短无权路径。AECFDGB111523277326数据结构与算法习题讲解(全)解析全文共97页，当前为第69页。解：(a)

(无权路径)A→B,A→C,A→B→G,A→B→E,A→C→D,A→B→E→F.(赋权路径)A→C,A→B,A→B→G,A→B→G→E,A→B→G→E→F,A→B→G→E→D.(b)(无权路径)B→C,B→E,B→G,B→C→D,B→E→F,B→C→D→A数据结构与算法习题讲解(全)解析全文共97页，当前为第70页。9.11找出第一题图中的网络最大流。解：首先沿路径:s,G,H,I,t发出4个单位的流，残余图如下:sDEFtCBAGHI222413341321342222123444数据结构与算法习题讲解(全)解析全文共97页，当前为第71页。其次，沿路径s,D,E,F,t发出3个单位的流，得残余图如下：sDEFtCBAGHI2224133413213122221234443数据结构与算法习题讲解(全)解析全文共97页，当前为第72页。接着，沿路径s,G,D,A,B,C,t发出2个单位的流,产生如下残余图:sDEFtCBAGHI22221334132111222123446322数据结构与算法习题讲解(全)解析全文共97页，当前为第73页。沿s,D,A,E,C,t发出1个单位的流:sDEFtCBAGHI22111334131122212344643311数据结构与算法习题讲解(全)解析全文共97页，当前为第74页。最后，沿路径s,A,E,C,t发出1个单位的流:sDEFtCBAGHI22213341312221234464342数据结构与算法习题讲解(全)解析全文共97页，当前为第75页。前面得到的残余图中没有s到t的路径。因此，算法终止。最终的流图负载了11个单位流，如下图所示:sDEFtCBAGHI222403340021342604043数据结构与算法习题讲解(全)解析全文共97页，当前为第76页。该流图不是唯一的。例如:沿路径G,D,A,E发出的2单位的流同样可以沿路径G,H,E发出。数据结构与算法习题讲解(全)解析全文共97页，当前为第77页。9.13一个二分图G=(V,E)是把V划分成两个子集V1和V2并且其边的两个顶点都不在同一个子集中的图。a)给出一个线性算法以确定一个图是否是二分图。b)二分匹配问题是找出E的最大子集E’使得没有顶点含在多于一条的边中。下图所示的是四条边的一个匹配（由虚线表示）。存在一个五条边的匹配，它是最大的匹配。指出二分匹配问题如何能够用于解决下列问题：我们有一组教师、一组课程，以及每位教师有资格教授的课程表。如果没有教师需要教授多于一门的课程，而且只有一位教师可以教授一门给定的课程，那么可以提供开设的课程的最多门数是多少？c)证明网络流问题可以用来解决二分匹配问题。*d)你对问题(b)的解法的时间复杂度如何？数据结构与算法习题讲解(全)解析全文共97页，当前为第78页。数据结构与算法习题讲解(全)解析全文共97页，当前为第79页。解：(a)假设一个图是连通无向的。假如它不是连通的,则对其连通分量使用该算法。开始时,标记所有顶点为未知。挑选任一顶点v,着红色,执行深度优先搜索。当一个结点被第一次访问到时,如果此次深度优先搜索是从红色顶点开始的，则将其着为蓝色，否则着为红色。如果在任一点，深度优先搜索遇到了同样颜色的顶点所构成的边，则该图不是二分图；反之，即是二分图。广度优先搜索(使用队列)亦可作用于此问题。此问题在本质上是二色着色问题，很明显是线性可解的。可与三色着色问题相比较，后者是NP完全问题。数据结构与算法习题讲解(全)解析全文共97页，当前为第80页。(b)构造一个无向图，它的一个顶点集对应每一位教师,一个顶点集对应每一门课程；如果一位教师v有资格教授一门课程w的话，则存在边(v,w)。即构成了一个二分图，如果有一个M条边的匹配就意味着有M门课程可以同时开课。数据结构与算法习题讲解(全)解析全文共97页，当前为第81页。(c)给二分图中的每条边赋权值1，并且从指出从教师点到课程点的每条边。加一顶点s，该顶点到所有教师顶点的边权值为1。加一顶点t，该顶点到所有课程顶点的边权值为1。则该网络的最大流量即为最大的匹配。数据结构与算法习题讲解(全)解析全文共97页，当前为第82页。*(d)运行时间是O(|E||V|half)因为此处是网络流问题的特殊情况。所有的边都有单位代价(值)，并且每一个顶点(除发点s和收点t)都有一个单位的indegree或outdegree。数据结构与算法习题讲解(全)解析全文共97页，当前为第83页。9.15a)使用Prim和Kruskal两种算法求出下图中的最小生成树。b)这棵最小生成树是唯一的吗？为什么？DAEFBGCHIJ3101263246524114138117数据结构与算法习题讲解(全)解析全文共97页，当前为第84页。解：一种可能的最小生成树如下所示，该方案不是唯一的。DAEFBGCHIJ31224217数据结构与算法习题讲解(全)解析全文共97页，当前为第85页。最小生成树的性质：1)最小生成树的边数必然是顶点数减一，|E|=|V|-1。2)最小生成树不可以有循环。3)最小生成树不必是唯一的。Prim算法与Kruskal算法是寻找最小生成树的经典方法，两者皆为贪心法，通常使用二元堆积，时间复杂度为O(ElgV)。Prim算法与Kruskal算法使用贪心法时有着相似的思维：一次“生成”一条“安全边”。数据结构与算法习题讲解(全)解析全文共97页，当前为第86页。9.21求出下图中图的所有割点。指出深度优先生成树和每个顶点的Num和Low的值。ACDBEFGHJIK数据结构与算法习题讲解(全)解析全文共97页，当前为第87页。解：从A开始进行深度优先搜索，按照字母表顺序依次访问邻接顶点。割点为C,E,F。C是割点是因为low[B]≥num[C];E是割点是因为low[H]≥num[E];F是割点是因为low[G]≥num[F];深度