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

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

其中，NlogN,Nlog(N2)有相同的增長(zhǎng)率。常見(jiàn)的幾種計(jì)算時(shí)間的關(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頁(yè)，當(dāng)前為第5頁(yè)。2.7對(duì)于下列六個(gè)程序片段中的每一個(gè)：給出運(yùn)行時(shí)間分析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頁(yè)，當(dāng)前為第6頁(yè)。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頁(yè)，當(dāng)前為第7頁(yè)。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)行時(shí)間復(fù)雜度分析為N*N2*N2,即O(N5).

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

=O(N2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{if(buf[i]!=0)//個(gè)人號(hào)碼不為0的時(shí)候

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

}}}}//while退出的時(shí)候只剩下一個(gè)人

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

優(yōu)點(diǎn)在于：編碼簡(jiǎn)單，并且如果被刪除的鍵在之后被重新插入（在同一位置），可以節(jié)省資源。缺點(diǎn)在于：需要更多的空間；因?yàn)槊恳粋€(gè)單元都需要額外的位（典型的如1byte）,且未使用的單元空間并沒(méi)有被釋放。(b)略數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁(yè)，當(dāng)前為第32頁(yè)。3.28雙端隊(duì)列是由某些項(xiàng)的一個(gè)表組成的數(shù)據(jù)結(jié)構(gòu)，對(duì)該數(shù)據(jù)結(jié)構(gòu)可以進(jìn)行下列操作：push(x):將項(xiàng)x插入雙端隊(duì)列的前端pop(x):從雙端隊(duì)列中刪除前端項(xiàng)并將其返回infect(x):將項(xiàng)x插入到雙端隊(duì)列的尾端eject():從雙端隊(duì)列中刪除尾端項(xiàng)并將其返回編寫(xiě)支持雙端隊(duì)列的例程，每種操作均花費(fèi)O(1)時(shí)間。數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁(yè)，當(dāng)前為第33頁(yè)。需要使用雙向鏈表，其上有指向頭結(jié)點(diǎn)和尾結(jié)點(diǎn)的指針。實(shí)際上可通過(guò)重命名鏈表的操作符，用一個(gè)鏈表實(shí)現(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頁(yè)，當(dāng)前為第34頁(yè)。3.35實(shí)現(xiàn)隊(duì)列的一種方法是使用一個(gè)循環(huán)鏈表，在循環(huán)鏈表中，最后一個(gè)結(jié)點(diǎn)的next指針指向第一個(gè)結(jié)點(diǎn)。假設(shè)該表不包括表頭，而且我們最多可保留一個(gè)迭代器，它對(duì)應(yīng)表中的一個(gè)結(jié)點(diǎn)。對(duì)于下列的哪種表示，所有基本隊(duì)列操作可以以常數(shù)最壞情況時(shí)間執(zhí)行？證明你的答案是正確的。a.保留一個(gè)迭代器，它對(duì)應(yīng)該表的第一項(xiàng)b.保留一個(gè)迭代器，它對(duì)應(yīng)該表的最后一項(xiàng)數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題講解(全)解析全文共97頁(yè)，當(dāng)前為第35頁(yè)。注：隊(duì)列是FIFO的(a)

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

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

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