本文格式為Word版，下載可任意編輯——數(shù)據(jù)結構課后習題答案第1章緒論

一、基礎知識題

1.1簡述以下概念

數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)類型，數(shù)據(jù)結構，規(guī)律結構，存儲結構，算法。數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符，以及所有能輸入到計算機中并被計算機程序識別和處理的符號的集合。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結點、頂點、記錄等。

數(shù)據(jù)類型是對數(shù)據(jù)的取值范圍、數(shù)據(jù)元素之間的結構以及允許施加操作的一種總體描述。每一種計算機程序設計語言都定義有自己的數(shù)據(jù)類型。

“數(shù)據(jù)結構〞這一術語有兩種含義，一是作為一門課程的名稱；二是作為一個科學的概念。作為科學概念，目前尚無公認定義，一般認為，探討數(shù)據(jù)結構要包括三個方面，一是數(shù)據(jù)的規(guī)律結構，二是數(shù)據(jù)的存儲結構，三是對數(shù)據(jù)進行的操作（運算）。而數(shù)據(jù)類型是值的集合和操作的集合，可以看作是已實現(xiàn)了的數(shù)據(jù)結構，后者是前者的一種簡化狀況。

數(shù)據(jù)的規(guī)律結構反映數(shù)據(jù)元素之間的規(guī)律關系（即數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系〞），數(shù)據(jù)的存儲結構是數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。數(shù)據(jù)的運算是對數(shù)據(jù)定義的一組操作，運算是定義在規(guī)律結構上的，和存儲結構無關，而運算的實現(xiàn)則依靠于存儲結構。

數(shù)據(jù)結構在計算機中的表示稱為物理結構，又稱存儲結構。是規(guī)律結構在存儲器中的映像，包括數(shù)據(jù)元素的表示和關系的表示。規(guī)律結構與計算機無關。

算法是對特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個或多個操作。一個算法應當具有以下特性：有窮性、確定性、可行性、輸入和輸出。

1.2數(shù)據(jù)的規(guī)律結構分哪幾種，為什么說規(guī)律結構是數(shù)據(jù)組織的主要方面？數(shù)據(jù)的規(guī)律結構分為線性結構和非線性結構。（也可以分為集合、線性結構、樹形結構和圖形即網(wǎng)狀結構）。

規(guī)律結構是數(shù)據(jù)組織的某種“本質(zhì)性〞的東西：（1）規(guī)律結構與數(shù)據(jù)元素本身的形式、內(nèi)容無關。（2）規(guī)律結構與數(shù)據(jù)元素的相對位置無關。（3）規(guī)律結構與所含數(shù)據(jù)元素的個數(shù)無關。

1.3試舉一個數(shù)據(jù)結構的例子，表達其規(guī)律結構、存儲結構、運算三方面的內(nèi)容。

學生成績表，規(guī)律結構是線性結構，可以順序存儲（也可以鏈式存儲），運算可以有插入、刪除、查詢，等等。

1.4簡述算法的五個特性，對算法設計的要求。

算法的五個特性是：有窮性、確定性、可行性、零至多個輸入和一至多個輸出。

對算法設計的要求：正確性，易讀性，頑強性，和高的時空間效率（運算速

度快，存儲空間小）。

1.5設n是正整數(shù)，求以下程序段中帶@記號的語句的執(zhí)行次數(shù)。

(1)i=1;k=0;(2)i=1;j=0;

while(ij)j++;@

}elsei++;}@

(3)x=y=0;(4)x=91;y=100;for(i=0;i0)for(j=0;j100)

{x++;@{x=x-10;y--;@

for(k=0;k4時，算法A2好于A1。

1.7選擇題：算法分析的目的是（）

A、找出數(shù)據(jù)結構的合理性B、研究算法中的輸入和輸出的關系C、分析算法的效率以求改進D、分析算法的易懂性和文檔特點C

二、算法設計題

1.8已知輸入x，y，z三個不相等的整數(shù)，設計一個“高效〞算法，使得這三個數(shù)按從小到大輸出。“高效〞的含義是用最少的元素比較次數(shù)、元素移動次數(shù)和輸出次數(shù)。

voidBest()

{//按序輸出三個整數(shù)的優(yōu)化算法inta,b,c,t;

scanf(“%d%d%d〞,

if(a>b)

{t=a;a=b;b=t:}//a和b已正序if(b>c)

{t=c;c=b;//c已到位

if(a>t){b=a;a=t;}//a和b已正序elseb=t;}

printf(“%d,%d,%d\\n〞,a,b,c);

//最正確2次比較，無移動；最差3次比較，7個賦值}

1.9在數(shù)組A[n]中查找值為k的元素，若找到則輸出其位置i(1≤i≤n)，否則輸出0作為標志。設計算法求解此問題，并分析在最壞狀況下的時間繁雜度。

從后向前查找，若找到與k值一致的元素則返回其位置，否則返回0。

intSearch(ElemTypeA[n+1],ElemTypek){i=n;

while(i>=1)if(i>=1)returni;elsereturn0;}

當查找不成功時，總的比較次數(shù)為n+1次，所以最壞狀況下時間繁雜度為O(n)。

在學過第9章“查找〞后，可優(yōu)化以上算法:設“監(jiān)視哨〞。算法如下：intSearch(ElemTypeA[n+1],ElemTypek){i=n;A[0]=k;

while(A[i]!=k)i--;returni;}

研究說明，當n>=1000時，算法效率提高50%。

第2章線性表

一、基礎知識題

2.1試述頭指針、頭結點、元素結點、首元結點的區(qū)別，說明頭指針和頭結點的作

指向鏈表第一個結點（或為頭結點或為首元結點）的指針稱為頭指針。“頭指針〞具有標識一個鏈表的作用，所以經(jīng)常用頭指針代表鏈表的名字，如鏈表L既是指鏈表的名字是L，也是指鏈表的第一個結點的地址存儲在指針變量L中，頭指針為“NULL〞則表示指針變量L沒指向任何鏈表。

有時，我們在整個線性鏈表的第一個元素結點之前參與一個結點，稱為頭結點，它的數(shù)據(jù)域可以不存儲任何信息（當然，作為“副產(chǎn)品〞，頭結點的數(shù)據(jù)域也可能做監(jiān)視哨或存放線性表的長度等附加信息），指針域中存放的是第一個數(shù)據(jù)結點的地址，空表時為空。“頭結點〞的參與，使插入和刪除等操作便利、統(tǒng)一。

元素結點即是數(shù)據(jù)結點，至少包括元素自身信息和其后繼元素的地址兩個域。

首元結點是指鏈表中第一個數(shù)據(jù)元素的結點；為了操作便利，尋常在鏈表的首元結點之前附設一個結點，稱為頭結點。

2.2分析順序存儲結構和鏈式存儲結構的優(yōu)缺點，說明何時應當利用何種結構。

①從空間上來看，當線性表的長度變化較大，難以估計其規(guī)模時，選用動態(tài)的鏈表作為存儲結構比較適合。由于鏈表除了需要設置數(shù)據(jù)域外，還要額外設置指針域，因此當線性表長度變化不大，易于事先確定規(guī)模時，為了儉約存儲空間，宜采用順序存儲結構。

②從時間上看，順序表具有按元素序號隨機訪問的特點，在順序表中按序號訪問數(shù)據(jù)元素的時間繁雜度為O(1)；而鏈表中按序號訪問的時間繁雜度為O(n)。所以假使經(jīng)常按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。

在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此n較大時順序表的插入和刪除效率低。在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作。從這個角度考慮顯然鏈表優(yōu)于順序表。

總之，兩種存儲結構各有長短，選擇那一種存儲結構，由實際問題中的主要因素決定。

2.3分析在順序存儲結構下插入和刪除結點時平均需要移動多少個結點。平均移動表中大約一半的結點。插入操作平均移動n2個結點，刪除操作平均移動(n?1)2個結點。具體移動的次數(shù)取決于表長和插入、刪除的結點的

位置。

2.4為什么在單循環(huán)鏈表中常使用尾指針，若只設頭指針，插入元素的時間繁雜度如何？

單循環(huán)鏈表中無論設置尾指針還是頭指針都可以遍歷到表中任一個結點。設置尾指針時，若在表尾進行插入元素或刪除第一元素，操作可在O(1)時間內(nèi)完成；若只設置頭指針，表尾進行插入或刪除操作，需要遍歷整個鏈表，時間繁雜度為O(n)。

2.5在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結點，能否刪除該結點，時間繁雜度如何？以上三種鏈表中，若知道指針p指向某結點，都能刪除該結點。

雙鏈表刪除p所指向的結點的時間繁雜度為O(1)，而單鏈表和單循環(huán)鏈表上刪除p所指向的結點的時間繁雜度均為O(n)。

2.6下面算法的功能是什么？

LinkedListUnknown(LinkedListla){LNode*q，*p;

if(lala=la->next;p=la;while(p->next)p=p->next;p->next=q;q->next=null;}

returnla;}

將首元結點刪除并插入到表尾（設鏈表長度大于1）。

2.7選擇題：在循環(huán)雙鏈表的*p結點之后插入*s結點的操作是（）

A、p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B、p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C、s->prior=p;s->next=p->next;p->next:=s;p->next->prior=s;

D、s->prior=p;s>next=p>next;p>next->prior=s;p->next=s;D

2.8選擇題：若某線性表最常用的操作是存取任一指定序號的元素和在最終進行

}

voiddigui(intn)

{if(n>0){printf(n);digui(n-1);}

}

3.8寫出以下中綴表達式的后綴表達式：

(1)A*B*C(2)(A+B)*C-D(3)A*B+C/(D-E)(4)(A+B)*D+E/(F+A*D)+C

解答】

(1)ABC**(2)AB+C*D-(3)AB*CDE-/+(4)AB+D*EFAD*+/+C+

3.9選擇題：循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為()。

A.rear=rear+1B.rear=(rear+1)%(m-1)

C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)D

3.11選擇題：4個園盤的Hahoi塔，總的移動次數(shù)為()。

A.7B.8C.15D.16C

3.12選擇題：允許對隊列進行的操作有()。

A.對隊列中的元素排序B.取出最近進隊的元素

C.在隊頭元素之前插入元素D.刪除隊頭元素D

二、算法設計題

3.13利用棧的基本操作，編寫求棧中元素個數(shù)的算法。將棧值元素出棧，出棧時計數(shù)，直至棧空。

intStackLength(StackS)

{//求棧中元素個數(shù)intn=0;

while(!StackEmpty(S){n++;Pop(S);}

returnn;}：若要求統(tǒng)計完元素個數(shù)后，不能破壞原來棧，則在計數(shù)時，將原

棧導入另一臨時棧，計數(shù)完畢，再將臨時棧倒入原棧中。intStackLength(StackS){//求棧中元素個數(shù)intn=0;

StackT;

StackInit(T);//初始化臨時棧T

while(!StackEmpty(S){n++;Push(T,Pop(S));}

while(!StackEmpty(T)

{Push(S,Pop(T));}

returnn;}

3.14雙向棧S是在一個數(shù)組空間V[m]內(nèi)實現(xiàn)的兩個棧，棧底分別處于數(shù)組

空間的兩端。試為此雙向棧設計棧初始化Init(S)、入棧Push(S，i，x)、出棧Pop(S，i)算法，其中i為0或1，用以指示棧號。

[題目分析]兩棧共享向量空間，將兩棧棧底設在向量兩端，初始時，s1棧頂指針為-1，s2棧頂為m。兩棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。

#defineElemTypeint∥假設元素類型為整型typedefstruct

{ElemTypeV[m];∥棧空間

inttop[2];∥top為兩個棧頂指針的數(shù)組}stk;

stkS;∥S是如上定義的結構類型變量，為全局變量(1)棧初始化intInit()

{S.top[0]=-1;S.top[1]=m;

return1;//初始化成功}

(2)入棧操作：

intpush(stkS,inti,intx)

∥i為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，失敗返回0

{if(i1){printf(“棧號輸入不對\\n〞);exit(0);}

if(S.top[1]-S.top[0]==1){printf(“棧已滿\\n〞);return(0);}switch(i)

{case0:S.V[++S.top[0]]=x;return(1);break;case1:S.V[--S.top[1]]=x;return(1);}

}∥push(3)退棧操作

ElemTypepop(stkS,inti)

∥退棧。i代表棧號，i=0時為左棧，i=1時為右棧。退棧成功時返回退

棧元素

∥否則返回-1

{if(i1){printf(“棧號輸入錯誤\\n〞)；exit(0);}switch(i)

{case0:if(S.top[0]==-1){printf(“棧空\\n〞)；return（-1）；}elsereturn(S.V[S.top[0]--]);

case1:if(S.top[1]==m{printf(“棧空\\n〞);return(-1);}elsereturn(S.V[S.top[1]++]);}∥switch}∥算法終止(4)判斷棧空

intEmpty();

{return(S.top[0]==-1}

[算法探討]請注意算法中兩棧入棧和退棧時的棧頂指針的計算。s1(左棧)是尋常意義下的棧，而s2(右棧)入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。

3.15設以數(shù)組Q[m]存放循環(huán)隊列中的元素，同時設置一個標志tag，以tag=0

和tag=1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空〞還是“不空〞。試編寫相應的入隊(QueueIn)和出隊(QueueOut)算法。（1）初始化

SeQueueQueueInit(SeQueueQ){//初始化隊列

Q.front=Q.rear=0;Q.tag=0;returnQ;

}（2）入隊

SeQueueQueueIn(SeQueueQ,inte){//入隊列

if((Q.tag==1)

Q.data[Q.rear]=e;

if(Q.tag==0)Q.tag=1;//隊列已不空

}returnQ;}

(3)出隊

ElemTypeQueueOut(SeQueueQ){//出隊列

if(Q.tag==0){printf(\隊列為空\\n\else

{Q.front=(Q.front+1)%m;

e=Q.data[Q.front];if(Q.front==Q.rear)Q.tag=0;//空隊列

}

return(e);}

3.16假設用變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含

元素的個數(shù)。試給出此循環(huán)隊列的定義，并寫出相應的入隊(QueueIn)和出隊(QueueOut)算法。（1）循環(huán)隊列的定義typedefstruct

{ElemTypeQ[m];∥循環(huán)隊列占m個存儲單元

intrear,length;∥rear指向隊尾元素,length為元素個數(shù)}SeQueue;(2)初始化

SeQueueQueueInit(SeQueuecq)

∥cq為循環(huán)隊列，本算法進行隊列初始化{cq.rear=0;cq.length=0;returncq;

}

(3)入隊

SeQueueQueueIn(SeQueuecq，ElemTypex)

∥cq是以如上定義的循環(huán)隊列，本算法將元素x入隊{if(cq.length==m)return(0);∥隊滿

else{cq.rear=(cq.rear+1)%m;∥計算插入元素位置

cq.Q[cq.rear]=x;∥將元素x入隊列

cq.length++;∥修改隊列長度}

return(cq);}（4）出隊

ElemTypeQueueOut(SeQueuecq)

∥cq是以如上定義的循環(huán)隊列，本算法是出隊算法，且返回出隊元素{if(cq.length==0)return(0);∥隊空

else{intfront=(cq.rear-cq.length+1+m)%m;∥出隊元素位置cq.length--;∥修改隊列長度return(cq.Q[front]);∥返回對頭元素

}

}

3.17已知Ackerman函數(shù)定義如下：

m?0?n?1?m?0,n?0Akm(m，n)=?akm(m?1,1)?akm(m?1,akm(m,n?1))m?0,n?0?試寫出遞歸和非遞歸算法。(1)遞歸算法

intAck(intm,n)

{if(m==0)return(n+1);

elseif(m!=0elsereturn(Ack(m-1,Ack(m,m-1));}

（2）非遞歸算法

intAckerman(intm,intn)

{intakm[m][n];

inti,j;

for(j=0;j

=pos;j--)

{*(p+x)=*p;p--;}∥串s的pos后的子串右移，空出串t的位置q--;∥指針q回退到串t的最終一個字符

for(j=1;jelse

s[j++]=s[i];

i++;

}∥while

i--;i=i/2;∥i先從’\\0’后退，然后其含義是第偶數(shù)字符的個數(shù)

while(i>0)

s[j++]=stk[i--]∥將第偶數(shù)個字符逆序填入原字符數(shù)組}

第5章數(shù)組和廣義表

一、基礎知識題

5.1已知二維數(shù)組A[3][5]，其每個元素占3個存儲單元，并且A[0][0]的存儲地址為1200。求元素A[1][3]的存儲地址（分別對以行序和列序為主序存儲進行探討），該數(shù)組共占用多少個存儲單元？依照以行序為主序存儲公式：

LOC(i，j)=LOC(c1，c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L在C語言中有：LOC(i，j)=LOC(0，0)+(i*(d2+1)+j)*L

則：LOC(A[1][3])=1200+(1*5+3)*3=1224(按行序存儲)LOC(A[1][3])=1200+(3*3+1)*3=1230(按列序存儲)

5.2有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，A[1][1]為第一元素，其存儲地址為1，每個元素占一個地址空間，求A[7][5]和A[5][6]的地址。

依照公式：

?i(i?1)?2?j當i?j1??i,j??nk??1??k??n(n?1)/2j(j?1)??i當i?j1??i,j??n?2LOC(A[7][5])=7(7-1)/2＋5=26

LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=20

5.3設有一個二維數(shù)組A[m][n]，設A[0][0]存放位置在644，A[2][2]存放位置在676，每個元素占一個空間，問A[3][3]存放在什么位置？

由于A[0][0]存放位置在644，A[2][2]存放位置在676，每個元素占一個空間，說明一行有15個元素（算法：（676－2－644）/2）。A[3][3]存放位置是692。

5.4二維數(shù)組A[9][10]的元素都是6個字符組成的串，請回復以下問題：

（1）存放A至少需要()個字節(jié)；

（2）A的第7列和第4行共占()個字節(jié)；

（3）若A按行存放，元素A[7][4]的起始地址與A按列存放時哪一個元素的起始地址一致。

依照題5.1給出的公式：

（1）存放A需要9*10*6=540個字節(jié)

（2）A的第7列和第4行共占(9+10-1)*6=108個字節(jié)

（3）LOC(A[7][4])=LOC(A[0][0])+[7*10+4]*L(按行序存儲)LOC(A[i][j])=LOC(A[0][0])+[j*9+i]*L（按列序存儲，

0

5.15選擇題：下面說法不正確的是:

A.廣義表的表頭總是一個廣義表B.廣義表的表尾總是一個廣義表

C.廣義表難以用順序存儲結構D.廣義表可以是一個多層次的結構

A

二、算法設計題

5.16設矩陣A中的某一個元素A[i][j]是第i行中的最小值，而又是第j列中的最大值，則稱A[i][j]為矩陣中的一個鞍點，請寫出一個可確定該鞍點位置的算法（假使這個鞍點存在），并給出算法的時間繁雜度。

尋覓馬鞍點最直接的方法,是在一行中找出一個最小值元素,然后檢查該元素是否是元素所在列的最大元素,如是,則輸出一個馬鞍點,時間繁雜度是O(m*(m+n)).本算法使用兩個輔助數(shù)組max和min,存放每列中最大值元素的行號和每行中最小值元素的列號,時間繁雜度為O（m*n+m），但比較次數(shù)比前種算法會增加，也多使用向量空間。

intm=10,n=10;

voidSaddle(intA[m][n])

∥A是m*n的矩陣,本算法求矩陣A中的馬鞍點

{inti,j,max[n]={0},∥max數(shù)組存放各列最大值元素的行號,初始化為行號0

min[m]={0};∥min數(shù)組存放各行最小值元素的列號,初始化為列號0

for(i=0;iA[i][j])min[i]=j;∥修改第i行最小元素的列號

}

for(i=0;iB.data[j].row)∥A的行號大于B的行號

{C.data[k].row=B.data[j].row;C.data[k].col=B.data[j].col;

C.data[k++].e=B.data[j++].e;}

else∥A的行號等于B的行號

if(A.data[i].colB.data[j].col)∥A的列號大于B

的列號

{C.data[k].row=B.data[j].row;C.data[k].col=B.data[j].col;C.data[k++].e=B.data[j++].e;}

else∥A的行、列號分別等于B的行、列號

{num=A.data[i++].e+B.data[j++].e;∥對應元素相加

if(num!=0)∥和不為0，則存入C中

{C.data[k].row=A.data[i].row;C.data[k].col=A.data[i].col;C.data[k++].e=num;}

}∥elseA的行、列號分別等于B的行、列號while(iC.data[k++].e=A.data[i++].e;}while(jtag!=0)//若是字表，則遞歸逆置{m=p->val.hp;

GListInvert(m,n);p->val.hp=n;};

r=p->tp;//保存后繼p->tp=q;q=p;

p=r//恢復當前待處理結點

}t=q;}

A#F#

后序遍歷二叉樹時結點的訪問序列。##D###ECB##FA

6.20有n個結點的k叉樹（k≥2）用k叉鏈表表示時，有多少個空指針？k叉樹（k≥2）用k叉鏈表表示時,每個結點有k個指針，除根結點沒有指針指向外，其余每個結點都有一個指針指向，故空指針的個數(shù)為：nk-(n-1)=n(k-1)+1

6.21一棵高度為h的滿k叉樹有如下性質(zhì)：根結點所在層次為0；第h層上的結點都是葉子結點；其余各層上每個結點都有k棵非空子樹，假使按層次自頂向下，同一層自左向右，順序從1開始對全部結點進行編號，試問：(1)各層的結點個數(shù)是多少?

(2)編號為i的結點的雙親結點（若存在）的編號是多少?

(3)編號為i的結點的第m個孩子結點（若存在）的編號是多少？

(4)編號為i的結點有右兄弟的條件是什么？其右兄弟結點的編號是多少？

(1)kl(l為層數(shù)，按題意，根結點為0層)

（2）由于該樹每層上均有kl個結點，從根開始編號為1，則結點i的從右向左數(shù)第２個孩子的結點編號為ki。設n為結點i的子女，則關系式(i-1)k+21)的前一結點編號為i-1（其最右邊子女編號是(i-1)*k+1），故結點i的第m個孩子的編號是(i-1)*k+1+m。

(4)根據(jù)以上分析，結點i有右兄弟的條件是，它不是雙親的從右數(shù)的第一子女，即(i-1)%k!=0，其右兄弟編號是i+1。

6.22．證明任一結點個數(shù)為n(n>0)的二叉樹的高度至少為?(logn)?+1。

最低高度二叉樹的特點是，除最下層結點個數(shù)不滿外，其余各層的結點數(shù)都應達到各層的最大值。設n個結點的二叉樹的最低高度是h，則n應滿足2h-1≦n≦2h-1關系式。解此不等式，并考慮h是整數(shù)，則有h=?logn?+1，即任一結點個數(shù)為n的二叉樹的高度至少為O(logn)。

6.23已知A[1..N]是一棵順序存儲的完全二叉樹，如何求出A[i]和A[j]的最近的共同祖先？根據(jù)順序存儲的完全二叉樹的性質(zhì)，編號為i的結點的雙親的編號是?i/2?，故A[i]和A[j]的最近公共祖先可如下求出：while(i/2!=j/2)

if(i>j)i=i/2;elsej=j/2;

退出while后，若i/2=0,則最近公共祖先為根結點，否則最近公共祖先是i/2。

6.24已知一棵滿二叉樹的結點個數(shù)為20到40之間的素數(shù)，此二叉樹的葉子結點有多少個？

結點個數(shù)在20到40的滿二叉樹且結點數(shù)是素數(shù)的數(shù)是31，其葉子數(shù)是16。

6.25求含有n個結點、采用順序存儲結構的完全二叉樹中的序號最小的葉子結點的下標。要求寫出簡要步驟。

根據(jù)完全二叉樹的性質(zhì)，最終一個結點（編號為n）的雙親結點的編號是?n/2?，這是最終一個分枝結點，在它之后是第一個終端（葉子）結點，故序號最小的葉子結點的下標是?n/2?+1。

6.26試證明:同一棵二叉樹的所有葉子結點，在前序序列、中序序列以及后序序列中都按一致的相對位置出現(xiàn)（即先后順序一致），例如前序abc，后序bca，中序bac。

前序遍歷是“根－左－右〞，中序遍歷是“左－根－右〞，后序遍歷是“左－右－根〞。三種遍歷中只是訪問“根〞結點的時機不同，對左右子樹均是按左右順序來遍歷的，因此所有葉子都按一致的相對位置出現(xiàn)。

6.27設具有四個結點的二叉樹的前序遍歷序列為ａｂｃｄ；Ｓ為長度等于4的由ａ，ｂ，ｃ，ｄ排列構成的字符序列，若任取Ｓ作為上述算法的中序遍歷序列，試問是否一定能構造出相應的二叉樹，為什么？試列出具有四個結點二叉樹的全部形態(tài)及相應的中序遍歷序列。

若前序序列是abcd，并非由這四個字母的任意組合（4!=24）都能構造出二叉樹。由于以abcd為輸入序列，通過棧只能得到1/(n+1)*2n!/(n!*n!)=14種，即以abcd為前序序列的二叉樹的數(shù)目是14。任取以abcd作為中序遍歷序列，并不全能與前序的abcd序列構成二叉樹。例如：若取中序序列dcab就不能。

該14棵二叉樹的形態(tài)及中序序列略。

6.28已知某二叉樹的每個結點，要么其左、右子樹皆為空，要么其左、右子樹皆不空。又知該二叉樹的前序序列為：JFDBACEHXIK；后序序列為：ACBEDXIHFKJ。請給出該二叉樹的中序序列，并畫出相應的二叉樹樹形。一般說來，僅僅知道二叉樹的前序遍歷序列和后序遍歷序列并不能確定這棵二叉樹，由于并不知道左子樹和右子樹兩部分各有多少個結點。但此題有特別性，即每個結點“要么其左、右子樹皆為空，要么其左、右子樹皆不空〞。具體說，前序序列的第一個結點是二叉樹的根，若該結點后再無其它結點，則二叉樹只有根結點；否則，該結點必有左右子樹，且根結點后的第一個結點就是“左子樹的根〞。到后序序列中查找這個“左子樹的根〞，它將后序序列分成左右兩部分：左部分(包括所查到的“左子樹的根結點〞)是二叉樹的左子樹(可能為空)，右部分(除去最終的根結點)則是右子樹(可能為空)。這樣，在確定根結點后，就可以將后序遍歷序列（從而也將前序遍歷序列）分成左子樹和右子樹兩部分了。

此題中，先看前序遍歷序列，第一個結點是J，所以J是二叉樹的根，J后面還有結點，說明J有左、右子樹，J后面的F必是左子樹的根。到后序遍歷序列中找到F,F將后序遍歷序列分成兩部分：左面ACBEDXIH，說明FACBEDXIH是根J的左子樹；右面K(K的右面J已知是根)，說明K是根J的右子樹。這樣，問題就轉化為“以前序序列FDBACEHXI和后序序列ACBEDXIHF去構造根J的左子樹〞，以及“以前序序列K和后序序列K去構造根J的右子樹〞了。如此構造下去，所構造的二叉樹如下。易見，中序序列為ABCDEFXHIJK。

J

KF

DHBEXI

CA

6.29已知一個森林的先序序列和后序序列如下，請構造出該森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK森林的先序序列