數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析

第一章1.5編寫一個遞歸方法，它返回數(shù)n的二進(jìn)制表示中1的個數(shù)。利用這樣的事實：如果n是奇數(shù)，那么它等于n/2的二進(jìn)制表示中1的個數(shù)加1。①intones(intn){if(n<2)returnn;returnn%2+ones(n/2);}數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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<<“所輸入整數(shù)中的二進(jìn)制中1的個數(shù)是：”<<j<<endl;return0;}數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第2頁。1.7證明下列公式a.logx<x對所有的x>0成立①數(shù)學(xué)歸納法：當(dāng)0<x≤1,命題顯然成立：x=1,公式是成立的；當(dāng)x<1時,logx是負(fù)數(shù)。同理可以很容易推出當(dāng)1<x≤2時命題成立：x=2,公式成立；當(dāng)x<2,logx最大為1。假設(shè)命題在p<x≤2p時成立(p為正整數(shù)),這時考慮有2p<Y≤4p(p≥1)。則logy=1+log(y/2)<1+y/2<y/2+y/2≤y,由此可推導(dǎo)出公式成立。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第3頁。②二項式法：令x=2x,有l(wèi)og2x<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;命題得證數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第4頁。第二章2.1按增長率排列函數(shù)：N,N1/2,N1.5,N2,NlogN,Nlog(logN),Nlog2N,Nlog(N2),2/N,2N,2N/2,37,N2logN,N3。指出哪些函數(shù)以相同的增長率增長。答：2/N,37,N1/2,N,Nlog(logN),NlogN,Nlog(N2),Nlog2N,N1.5,N2,N2logN,N3,2N/2,2N.

其中，NlogN,Nlog(N2)有相同的增長率。常見的幾種計算時間的關(guān)系：

O(1)<O(logN)<O(N)<O(NlogN)<O(N2)<O(N3)O(2N)<O(N!)<O(NN)數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第5頁。2.7對于下列六個程序片段中的每一個：給出運(yùn)行時間分析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)數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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)數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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可等規(guī)模于i2,同樣也等規(guī)模于N2.k等規(guī)模于j,即N2.則該程序段的運(yùn)行時間復(fù)雜度分析為N*N2*N2,即O(N5).

數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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語句的循環(huán)次數(shù)為“12+22+32+…+n2”,如上題所述if語句至多要執(zhí)行N3次,但是實際上只有O(N2)次(因為對每一個i，實際上都嚴(yán)格執(zhí)行了i次),因此最內(nèi)的循環(huán)只執(zhí)行了O(N2)次。而每執(zhí)行一次,將花費(fèi)O(j2)

=O(N2)

的時間,總數(shù)即為O(N4)。個人理解：

if(j%i==0)for(k=0;k<j;k++)sum++;這段程序段的循環(huán)次數(shù)O(N)數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第9頁。2.8假設(shè)需要生成n個自然數(shù)的一個隨機(jī)置換。例如：{4,3,1,5,2}和{3,1,4,2,5}就是合法的置換，但{5,4,1,2,1}則不是，因為數(shù)1出現(xiàn)2次而數(shù)3卻沒有。這種程序常常用于模擬一些算法。我們假設(shè)存在一個隨機(jī)數(shù)生成器n，它用方法randInt(i,j)以相同的概率生成i和j之間的一個整數(shù)。下面是三個算法：

(1).如下填入從a[0]到a[n-1]的數(shù)組a:為了填入a[i],生成隨機(jī)數(shù)直到它不同于已經(jīng)生成的一個a[0],a[1],…,a[i-1]時再將其填入；

(2).同算法(1)，但是要使用一個附加的數(shù)組，稱之為used數(shù)組。當(dāng)一個隨機(jī)數(shù)ran最初被放入數(shù)組a的時候，設(shè)置used[ran]=ture。就是說，當(dāng)一個隨機(jī)數(shù)填入a[i]時，可以用一步來測試是否該隨機(jī)數(shù)已經(jīng)被使用，而不是像第一個算法那樣可能用i步來測試；

(3).填寫該數(shù)組，使得a[i]=i+1，然后for(i=1;i<n;i++)swap(a[i],a[randInt(0,i)]);試問：

a.證明這三個算法都生成合法的置換，并且所以的置換都是等可能的；

b.對每個算法都給出你能夠得出的盡可能不同的期望運(yùn)行時間分析；

c.沒個算法的最壞情形的運(yùn)行時間是什么？數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第10頁。答：a.所有的算法都可以生成合法的置換。很明顯，前2個算法在測試中可以保證不生成重復(fù)的數(shù)，并且它們是完全隨機(jī)的，故它們生成的置換是等可能。第3個算法輪換數(shù)組中的元素，這個數(shù)組最初是沒有重復(fù)數(shù)的，也不會存在非法置換。前2個算法很明顯成立，第3個算法可以用數(shù)學(xué)歸納法證明，詳細(xì)證明如下：數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第11頁。1.當(dāng)n=1時，a[0]=1，都是100%，成立；2.當(dāng)n=2時，for(i=1;i<n;++i)swap(a[i],a[randInt(0,i)]);

第一次循環(huán)，當(dāng)i=1時，即a[0]=1,a[i]=a[1]；3.當(dāng)n=3時，第二次循環(huán)時，當(dāng)i=2時，此時有兩種可能，原序列為0,1;1,0的幾率各為50%。randInt(0,2)可能為0,1,2的幾率各為1/3。此時,原序列為0,1時,randInt(0,2)為0,那么此序列經(jīng)過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.假設(shè)此命題在n=k時成立，那么就是說，ｋ前面序列共有序列k-1種，且所有序列的幾率為1/((k-1)*k)。5.當(dāng)n=k+1時,第k+1次循環(huán)時,前面序列正好為n=k時的情況,此時i=k.randInt(0,k)共可能為0~k,k+1種可能。所以以前的每個可能序列在置換后有k+1種可能，而以前共有k種等可能序列，那么最后可能的序列為k*(k+1)種可能，并且，因為原序列為等可能的，每個等可能序列產(chǎn)生的序列都是k+1種，所以最后的序列也是等可能的。而當(dāng)n=k+1時，應(yīng)該共有=(k+1)*k種，所以，此命題得證。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第12頁。注：證明時默認(rèn)地利用了一個命題：當(dāng)原序列為互不相等的等可能序列時，新加入一個與原來序列任何數(shù)值都不相等的數(shù)值，無論這個數(shù)值放在原序列的哪個位置，都不可能使原不相等的序列相等。例：210,021,012,201,120,102，這時加入一個新的數(shù)值3，無論把3插入序列的哪個位置，因為原來序列的排列不相等，所以，他們還是不會相等，這樣，才保證了最后k個序列的k+1種可能都不相等，不會重復(fù)。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第13頁。b.第一個算法中，決定a[i]中一個之前沒有使用過的隨機(jī)數(shù)是否被填入的時間是O(i)。在那些需要測試的隨機(jī)數(shù)中，需要產(chǎn)生期望的隨機(jī)數(shù)的次數(shù)為N/(N?i)次。得出結(jié)論如下：n個數(shù)中有i個可能是重復(fù)的。因此，置換成功的概率為(N?i)/N。因此，在獨(dú)立的測試中，期望數(shù)為N/(N?i)。時間復(fù)雜度即為：數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第14頁。第2個算法為每個隨機(jī)數(shù)保留了因子i，因此，時間度平均減少到了O(NlogN)

。第3個算法很明顯是線性的，O(N)。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第15頁。c.算法1和算法2的最壞運(yùn)行時間無法被界定，在一直隨機(jī)到重復(fù)數(shù)字的時候可以到達(dá)無限大。算法3的運(yùn)行時間是線性的——它的運(yùn)行時間并不依賴于隨機(jī)數(shù)的次序。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第16頁。2.12一個算法對于大小為100的輸入花費(fèi)0.5ms，如果運(yùn)行時間如下：則用1min可以解決多大的問題(設(shè)低階項可以忽略)。

a.是線性的；b.為O(NlogN)c.是二次的；d.是三次的數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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可得數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第18頁。2.18數(shù)值分析中一個重要的問題是對某一個任意的函數(shù)f找出方程f(x)=0的一個解。如果該函數(shù)是連續(xù)的，并有兩個點(diǎn)low和hign使得f(low)和f(high)符號相反，那么在low與high之間必然存在一個根。并且這個根可以通過二分搜索求得。寫一個函數(shù)，以f,low和high為參數(shù)，并且解出一個零點(diǎn)。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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);}為使程序正常終止，必須設(shè)置基準(zhǔn)情況。（注意精度防止溢出）數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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); }}數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第21頁。2.26大小為N的數(shù)組A，其主元素是一個出現(xiàn)超過N/2次的元素(從而這樣的元素最多有一個)。例如：數(shù)組：3,3,4,2,4,4,2,4,4有一個主元素4；而數(shù)組3,3,4,2,4,4,2,4沒有主元素。如果沒有主元素，那么你的程序應(yīng)該指出來。a.遞歸如何終止？

b.當(dāng)N是奇數(shù)時的情形如何處理？

c.該算法的運(yùn)行時間是多少？

d.我們?nèi)绾伪苊馐褂酶郊訑?shù)組B？數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第22頁。a.如果只有2個或更少的元素，不需要遞歸。

b.一種方法是：標(biāo)記，如果前N-1個元素已經(jīng)出現(xiàn)主元素，則最后一個元素不需要考慮。否則，最后一個元素有可能是主元素。因此當(dāng)N是奇數(shù)時，忽略最后一個元素。像之前一樣運(yùn)行算法。如果沒有主元素出現(xiàn)，則將第N個元素作為候選值返回。c.運(yùn)行時間為O(N),并且滿足T(N)=T(N/2)+O(N)。d.保存一份數(shù)據(jù)到數(shù)組B。之后，通過復(fù)制每一個Bi到數(shù)組A即可避免遞歸。區(qū)別在于原遞歸策略將要用到O(logN)個數(shù)組，現(xiàn)在只需要用2個。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第23頁。第三章鏈表、堆棧、隊列3.2通過只調(diào)整鏈而不是數(shù)據(jù)來交換兩個相鄰的元素使用。a.單向鏈表b.雙向鏈表數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第26頁。3.6Josephus問題是下面一個游戲：有N個人坐成一圈，編號為1至N。從編號為1的人開始傳遞熱馬鈴薯。M次傳遞之后，持有馬鈴薯的人退出游戲，圈縮小，然后游戲從退出的下面的人開始繼續(xù)，最終留下的獲勝。這樣M=0且N=5，那么參加游戲的人依次退出，5號獲勝。a.寫出一個程序來解決Josephus問題，此時M和N為任意值，盡可能使程序高效，同時確保存儲單元被正確處理。b.程序運(yùn)行時間是多少？c.當(dāng)M=1時，程序運(yùn)行時間是多少？對于N的較大值（N>100000），delete例程對程序運(yùn)行速度的影響有多大？數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第27頁。分析：Thisisastandardprogrammingproject.ThealgorithmcanbespedupbysettingM’=MmodN,sothatthehotpotatonevergoesaroundthecirclemorethanonce.IfM>N/2,thepotatoshouldbepassedinthereversedirection.Thisrequiresadoublylinkedlist.TheworstcaserunningtimeisclearlyO(Nmin(M,N)),althoughwhentheheuristicsareused,andMandNarecomparable,thealgorithmmightbesignificantlyfaster.IfM=1,thealgorithmisclearlylinear.數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第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;}數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第29頁。解（2）：voidfindout(intn,intm){intbuf[max];intdex=0;intin=0;for(inti=1;i<=n;i++)//n是人數(shù)

{buf[i]=i;//給n個人賦號碼}while(n>in+1)//剩下人數(shù)大于1的時候才執(zhí)行

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

{if(buf[i]!=0)//個人號碼不為0的時候

{dex++;if(dex==m)//若是數(shù)到m,{buf[i]=0;//則把此人的號碼改成0in++;//出圈人的個數(shù)加1dex=0;//判斷值清0,從新開始找

}}}}//while退出的時候只剩下一個人

for(i=1;i<=n;i++)if(buf[i]!=0)printf(“最后獲勝者號碼為:%d\n",buf[i]);}數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第30頁。3.20不同于我們已經(jīng)給出的刪除方法，另一種是使用懶惰刪除的方法。為刪除一個元素，我們只是標(biāo)記元素被刪除表中被刪除和未被刪除元素的個數(shù)作為數(shù)據(jù)結(jié)構(gòu)的一部分被保留。如果被刪除元素和未被刪除元素一樣多，則遍歷整個表，對所有被標(biāo)記的結(jié)點(diǎn)執(zhí)行標(biāo)準(zhǔn)的刪除算法。a.列出懶惰刪除的優(yōu)點(diǎn)和缺點(diǎn)b.寫出使用懶惰刪除實現(xiàn)標(biāo)準(zhǔn)鏈表操作的例程。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第31頁。(a)

優(yōu)點(diǎn)在于：編碼簡單，并且如果被刪除的鍵在之后被重新插入（在同一位置），可以節(jié)省資源。缺點(diǎn)在于：需要更多的空間；因為每一個單元都需要額外的位（典型的如1byte）,且未使用的單元空間并沒有被釋放。(b)略數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第32頁。3.28雙端隊列是由某些項的一個表組成的數(shù)據(jù)結(jié)構(gòu)，對該數(shù)據(jù)結(jié)構(gòu)可以進(jìn)行下列操作：push(x):將項x插入雙端隊列的前端pop(x):從雙端隊列中刪除前端項并將其返回infect(x):將項x插入到雙端隊列的尾端eject():從雙端隊列中刪除尾端項并將其返回編寫支持雙端隊列的例程，每種操作均花費(fèi)O(1)時間。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第33頁。需要使用雙向鏈表，其上有指向頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的指針。實際上可通過重命名鏈表的操作符，用一個鏈表實現(xiàn)。

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;};數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第34頁。3.35實現(xiàn)隊列的一種方法是使用一個循環(huán)鏈表，在循環(huán)鏈表中，最后一個結(jié)點(diǎn)的next指針指向第一個結(jié)點(diǎn)。假設(shè)該表不包括表頭，而且我們最多可保留一個迭代器，它對應(yīng)表中的一個結(jié)點(diǎn)。對于下列的哪種表示，所有基本隊列操作可以以常數(shù)最壞情況時間執(zhí)行？證明你的答案是正確的。a.保留一個迭代器，它對應(yīng)該表的第一項b.保留一個迭代器，它對應(yīng)該表的最后一項數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第35頁。注：隊列是FIFO的(a)

在尾結(jié)點(diǎn)插入時，不能以常數(shù)時間執(zhí)行。(b)

因為是循環(huán)鏈表,我們可以以常數(shù)時間訪問鏈表前端,因此b情況可以。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第36頁。第四章樹4.2對于圖中樹上的結(jié)點(diǎn)（每一個），a.指出它的父結(jié)點(diǎn)b.列出它的兒子、兄弟c.算出它的深度高度ABCDFEJGHKILM數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第37頁。解：對任意一個結(jié)點(diǎn)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}數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第38頁。4.8給出對應(yīng)圖中的樹的前綴表達(dá)式，中綴表達(dá)式以及后綴表達(dá)式。解：前綴表達(dá)式：-**ab+cde中綴表達(dá)式：((a*b)*(c+d))-e后綴表達(dá)式：ab*cd+*e--*e*+dabc數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第39頁。4.9題：a.指出將[3，1，4，6，9，2，5，7]插入到初始為空的二叉查找樹中的結(jié)果b.指出刪除根后的結(jié)果解：314297565416279數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第40頁。4.27指出依序訪問圖中伸展樹鍵3，9，1，5后的結(jié)果10111312462135879數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第41頁。解：Afteraccessing3,（第一次旋轉(zhuǎn)后，呈“一字形”）31210111213468579數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第42頁。Afteraccessing9,（經(jīng)旋轉(zhuǎn)后，最后一次呈“之字形展開”）31210111213468579數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第43頁。Afteraccessing1,（“一字形”）16857101112139324數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第44頁。Afteraccessing5,（“一字形”……“之字形”）18571011121393246數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第45頁。4.43指出如何用兒子/兄弟鏈實現(xiàn)方法表示圖中的樹ABGJKLCNFDEIHMOPQR數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第46頁。ABDHEIJCFKLOMPQRGN解：數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第47頁。6.2題：a.寫出一個一次將10，12，1，14，6，5，8，15，3，9，7，4，11，13和2插入到一個初始為空的二叉堆中的結(jié)果b.寫出使用相同的輸入通過線性時間算法建立一個二叉堆的結(jié)果。第六章優(yōu)先隊列（堆）數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第48頁。解：（1）堆排序；（2）下濾132675415141291011138132126481514975111310數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第49頁。6.3寫出對上面練習(xí)中的堆執(zhí)行3次deletMin操作后的結(jié)果：解：465127108151491311465137108151412911數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第50頁。6.15設(shè)一個d堆初始化時有N個元素，而我們需要對其執(zhí)行M次percolateUp(上濾)和N次deleteMin（刪除最小元）。a.用M、N和d表示的所有操作的總運(yùn)行時間是多少：b.如果d=2，所有的堆操作的運(yùn)行時間是多少？c.如果d=O(N)，總的運(yùn)行時間是多少？*d.怎樣選擇d將使總的運(yùn)行時間最小？數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第51頁。(a)O((M+dN)logdN).(b)O((M+N)logN).(c)O(M+N2).(d)d=max(2,M/N).數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第52頁。6.19合并圖中的兩個左式堆21112171858154961018311121數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第53頁。解：24951018318156112111121718數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第54頁。6.27寫出將鍵1到15依次插入到一斜堆內(nèi)的結(jié)果。解：132756415111391410128數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第55頁。6.32將圖中的兩個二項隊列合并。13235124651221246514161826415182552911數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第56頁。解：25529114181513235124651221246514261618數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第57頁。第七章排序7.1使用插入排序?qū)⑿蛄?,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數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第58頁。7.4寫出使用增量{1,3,7}對輸入數(shù)據(jù)9,8,7,6,5,4,3,2,1運(yùn)行希爾排序得到的結(jié)果。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數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第59頁。7.11指出堆排序如何處理輸入數(shù)據(jù)142,543,123,65,453,879,572,434,111,242,811,102。解：輸入數(shù)據(jù)為：142,543,123,65,453,879,572,434,111,242,811,102堆化后輸出的結(jié)果為：879,811,572,434,543,123,142,65,111,242,453,102把堆頂元素879輸出并置于堆的末尾。這里用斜體表示以說明它已不是堆的一部分。將102替代原堆頂?shù)奈恢貌⑦M(jìn)行比較調(diào)整后，得:811,543,572,434,453,123,142,65,111,242,102,879數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第60頁。反復(fù)進(jìn)行上述過程，可得：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數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第61頁。7.15用歸并排序?qū)?,1,4,1,5,9,2,6排序解：首先設(shè)前半部分序列{3,1,4,1}是已排序的。對其,設(shè)序列{3,1}是已排序的。該序列包含了序列基準(zhǔn)情形{3}和{1},則可通過歸并結(jié)果得到{1,3}。序列{4,1}可同樣地排序為{1,4}。這樣即可將兩序列歸并得到{1,1,3,4}。相應(yīng)的設(shè)后半部分序列是已排序的，用類似的排序方法,可逐步得到序列{2,5,6,9}.最終再將兩部分序列用歸并算法合并到一起，易得{1,1,2,3,4,5,6,9}。歸并算法則是一種經(jīng)典的分治策略數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第62頁。7.19用三數(shù)中值分割法以及截止為3的快速排序?qū)?,1,4,1,5,9,2,6,5,3,5排序。解：原輸入為：3,1,4,1,5,9,2,6,5,3,5對左段、中間位置和右端元素進(jìn)行排序后，得到：3,1,4,1,5,5,2,6,5,3,9因此，樞紐元為5，交換使樞紐元離開得到：3,1,4,1,5,3,2,6,5,5,9數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第63頁。第一次交換在兩個5之間進(jìn)行。第二次交換時i和交錯j，此時樞紐元與i進(jìn)行交換得:3,1,4,1,5,3,2,5,5,6,9對前8個元素遞歸地進(jìn)行快速排序:3,1,4,1,5,3,2,5對三數(shù)進(jìn)行排序得: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已經(jīng)交錯，故不再交換。此時i指向5，則樞紐元與其交換得:1,1,3,2,3,4,5,5數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第64頁。調(diào)用遞歸對上述序列的前4個元素進(jìn)行排序，得其樞紐元為1,且分割段沒有改變。因子序列低于截止,故不進(jìn)行操作。類似的，最后3個元素構(gòu)成了一個基準(zhǔn)情形,不進(jìn)行操作。現(xiàn)在加入后面的3個元素，對右邊子序列進(jìn)行快速排序，因其只有3個元素，故不進(jìn)行操作。得到：1,1,3,2,3,4,5,5,5,6,9其中，對截止范圍內(nèi)的小數(shù)組進(jìn)行了插入排序。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第65頁。7.28當(dāng)實現(xiàn)快速排序時，如果數(shù)組包含許多重復(fù)元，那么可能更好的方法是執(zhí)行3路劃分(劃分成小于、等于以及大于樞紐元的三部分元素)以進(jìn)行更小的遞歸調(diào)用。假設(shè)有如compareTo方法提供的3路比較。a)給出一個算法，該算法只使用N-1次3路比較而將一個N元素子數(shù)組實施3路原位劃分。如果有d項等于樞紐元，那么可以使用d次附加的Comparable交換，高于和超越2路分割算法(提示：隨著i和j彼此相向移動，保持5組元素如下)：EQUALSMALLUNKNOWNLARGEEQUALijb)證明，使用上面的算法將只含有d個不同值的N元素數(shù)組排序花費(fèi)O(dN)時間。（詳解略）參見J.L.BentleyandM.D.McElroy,“EngineeringaSortFunction,”Software—PracticeandExperience數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第66頁。第九章9.1找出下圖的一個拓?fù)渑判騭DEFtCBAGHI222413341321342626163數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第67頁。解：下列排序是通過隊列獲得的，且頂點(diǎn)在鄰接表中是以字母順序出現(xiàn)的。此拓?fù)渑判驗椋簊,G,D,H,A,B,E,I,F,C,t數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第68頁。9.5a)找出下圖中A點(diǎn)到所有其他頂點(diǎn)的最短路徑。b)找出下圖中B點(diǎn)到所有其他頂點(diǎn)的最短無權(quán)路徑。AECFDGB111523277326數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第69頁。解：(a)

(無權(quán)路徑)A→B,A→C,A→B→G,A→B→E,A→C→D,A→B→E→F.(賦權(quán)路徑)A→C,A→B,A→B→G,A→B→G→E,A→B→G→E→F,A→B→G→E→D.(b)(無權(quán)路徑)B→C,B→E,B→G,B→C→D,B→E→F,B→C→D→A數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第70頁。9.11找出第一題圖中的網(wǎng)絡(luò)最大流。解：首先沿路徑:s,G,H,I,t發(fā)出4個單位的流，殘余圖如下:sDEFtCBAGHI222413341321342222123444數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第71頁。其次，沿路徑s,D,E,F,t發(fā)出3個單位的流，得殘余圖如下：sDEFtCBAGHI2224133413213122221234443數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第72頁。接著，沿路徑s,G,D,A,B,C,t發(fā)出2個單位的流,產(chǎn)生如下殘余圖:sDEFtCBAGHI22221334132111222123446322數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第73頁。沿s,D,A,E,C,t發(fā)出1個單位的流:sDEFtCBAGHI22111334131122212344643311數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第74頁。最后，沿路徑s,A,E,C,t發(fā)出1個單位的流:sDEFtCBAGHI22213341312221234464342數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第75頁。前面得到的殘余圖中沒有s到t的路徑。因此，算法終止。最終的流圖負(fù)載了11個單位流，如下圖所示:sDEFtCBAGHI222403340021342604043數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第76頁。該流圖不是唯一的。例如:沿路徑G,D,A,E發(fā)出的2單位的流同樣可以沿路徑G,H,E發(fā)出。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第77頁。9.13一個二分圖G=(V,E)是把V劃分成兩個子集V1和V2并且其邊的兩個頂點(diǎn)都不在同一個子集中的圖。a)給出一個線性算法以確定一個圖是否是二分圖。b)二分匹配問題是找出E的最大子集E’使得沒有頂點(diǎn)含在多于一條的邊中。下圖所示的是四條邊的一個匹配（由虛線表示）。存在一個五條邊的匹配，它是最大的匹配。指出二分匹配問題如何能夠用于解決下列問題：我們有一組教師、一組課程，以及每位教師有資格教授的課程表。如果沒有教師需要教授多于一門的課程，而且只有一位教師可以教授一門給定的課程，那么可以提供開設(shè)的課程的最多門數(shù)是多少？c)證明網(wǎng)絡(luò)流問題可以用來解決二分匹配問題。*d)你對問題(b)的解法的時間復(fù)雜度如何？數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第78頁。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第79頁。解：(a)假設(shè)一個圖是連通無向的。假如它不是連通的,則對其連通分量使用該算法。開始時,標(biāo)記所有頂點(diǎn)為未知。挑選任一頂點(diǎn)v,著紅色,執(zhí)行深度優(yōu)先搜索。當(dāng)一個結(jié)點(diǎn)被第一次訪問到時,如果此次深度優(yōu)先搜索是從紅色頂點(diǎn)開始的，則將其著為藍(lán)色，否則著為紅色。如果在任一點(diǎn)，深度優(yōu)先搜索遇到了同樣顏色的頂點(diǎn)所構(gòu)成的邊，則該圖不是二分圖；反之，即是二分圖。廣度優(yōu)先搜索(使用隊列)亦可作用于此問題。此問題在本質(zhì)上是二色著色問題，很明顯是線性可解的。可與三色著色問題相比較，后者是NP完全問題。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第80頁。(b)構(gòu)造一個無向圖，它的一個頂點(diǎn)集對應(yīng)每一位教師,一個頂點(diǎn)集對應(yīng)每一門課程；如果一位教師v有資格教授一門課程w的話，則存在邊(v,w)。即構(gòu)成了一個二分圖，如果有一個M條邊的匹配就意味著有M門課程可以同時開課。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第81頁。(c)給二分圖中的每條邊賦權(quán)值1，并且從指出從教師點(diǎn)到課程點(diǎn)的每條邊。加一頂點(diǎn)s，該頂點(diǎn)到所有教師頂點(diǎn)的邊權(quán)值為1。加一頂點(diǎn)t，該頂點(diǎn)到所有課程頂點(diǎn)的邊權(quán)值為1。則該網(wǎng)絡(luò)的最大流量即為最大的匹配。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第82頁。*(d)運(yùn)行時間是O(|E||V|half)因為此處是網(wǎng)絡(luò)流問題的特殊情況。所有的邊都有單位代價(值)，并且每一個頂點(diǎn)(除發(fā)點(diǎn)s和收點(diǎn)t)都有一個單位的indegree或outdegree。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第83頁。9.15a)使用Prim和Kruskal兩種算法求出下圖中的最小生成樹。b)這棵最小生成樹是唯一的嗎？為什么？DAEFBGCHIJ3101263246524114138117數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第84頁。解：一種可能的最小生成樹如下所示，該方案不是唯一的。DAEFBGCHIJ31224217數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第85頁。最小生成樹的性質(zhì)：1)最小生成樹的邊數(shù)必然是頂點(diǎn)數(shù)減一，|E|=|V|-1。2)最小生成樹不可以有循環(huán)。3)最小生成樹不必是唯一的。Prim算法與Kruskal算法是尋找最小生成樹的經(jīng)典方法，兩者皆為貪心法，通常使用二元堆積，時間復(fù)雜度為O(ElgV)。Prim算法與Kruskal算法使用貪心法時有著相似的思維：一次“生成”一條“安全邊”。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第86頁。9.21求出下圖中圖的所有割點(diǎn)。指出深度優(yōu)先生成樹和每個頂點(diǎn)的Num和Low的值。ACDBEFGHJIK數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁，當(dāng)前為第87頁。解：從A開始進(jìn)行深度優(yōu)先搜索，按照字母表順序依次訪問鄰接頂點(diǎn)。割點(diǎn)為C,E,F。C是割點(diǎn)是因為low[B]≥num[C];E是割點(diǎn)是因為low[H]≥num[E];F是割點(diǎn)是因為low[G]≥num[F];深度