《算法與數(shù)據(jù)結(jié)構(gòu)》習題集及答案

《算法與數(shù)據(jù)結(jié)構(gòu)》習題集及答案

習題1

1-1.數(shù)據(jù)的邏輯結(jié)構(gòu)為：MyDS={D,R},其中:

D={a,b,c,,d,e,f}

R={<a,b>,<a,c>,<a,d>,<a,e>,<a,f>,<b,c>,<b,d>,<b,e>,<b,f>,<c,d>,<c,e>,<c,f>,

<d,e>,<d,f>,<e,f>}

請畫出它的結(jié)構(gòu)圖。它是線性結(jié)構(gòu)嗎？哪些結(jié)點是開始結(jié)點？哪些結(jié)點是終端結(jié)點？

答案：

它不是線性結(jié)構(gòu)，a結(jié)點是開始結(jié)點，f結(jié)點是終端結(jié)點。

1-2.試說明基本數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的聯(lián)系與差異。

答案：

數(shù)據(jù)結(jié)構(gòu)所研究內(nèi)容的著重點主要體現(xiàn)在三個方面：

第一是數(shù)據(jù)間的邏輯關(guān)系，即數(shù)據(jù)元素之間的關(guān)系。

第二是數(shù)據(jù)的存儲關(guān)系，即數(shù)據(jù)在計算機中的存儲結(jié)構(gòu)。

第三是算法，即定義在數(shù)據(jù)對象上的操作的實現(xiàn)策略，是對操作的描述。

因此，簡單說來，數(shù)據(jù)結(jié)構(gòu)所研究的問題是如何將現(xiàn)實世界中的事物合理描述為計算機

世界中所研究的對象，并根據(jù)研究對象的特點，分析對象之間的關(guān)系、存儲結(jié)構(gòu)和操作的學

科。

基本數(shù)據(jù)類型（DataType）：數(shù)據(jù)是按照數(shù)據(jù)結(jié)構(gòu)分類的，具有相同數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)

屬同一類。同一類數(shù)據(jù)的全體稱為一個數(shù)據(jù)類型。在程序設(shè)計高級語言中，數(shù)據(jù)類型用來說

明一個數(shù)據(jù)在數(shù)據(jù)分類中的歸屬。它是數(shù)據(jù)的一種屬性。這個屬性限定了該數(shù)據(jù)的變化范圍。

高級語言中都有基本數(shù)據(jù)類型。例如在C、C++和Java語言中，有基本類型int（整型）、float

（浮點型）和char（字符型），有構(gòu)造類型數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型和自定義等。

抽象數(shù)據(jù)類型即不論其內(nèi)部結(jié)構(gòu)如何變化，只要數(shù)學特性不變，都不影響抽象數(shù)據(jù)類型

外部的使用。是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取

決于抽象數(shù)據(jù)類型的邏輯特性，與它在計算機內(nèi)部如何表示和實現(xiàn)無關(guān)。

1-3.為什么要引入抽象數(shù)據(jù)類型概念，它有什么特點？

答案：引入抽象數(shù)據(jù)類型的目的是把數(shù)據(jù)類型的表示和數(shù)據(jù)類型上運算的實現(xiàn)與這些數(shù)據(jù)類

型和運算在程序中的引用隔開，使它們相互獨立。

抽象數(shù)據(jù)類型的定義僅取決于抽象數(shù)據(jù)類型的邏輯特性，與它在計算機內(nèi)部如何表示和實現(xiàn)

無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要數(shù)學特性不變，都不影響抽象數(shù)據(jù)類型外部的使用。

1-4.請用抽象數(shù)據(jù)類型描述法描述一個隨身聽，再用C、C++或Java描述。

答案：

隨身聽可用來放歌，也可以快進和快退，還可以停止，所以隨身聽的抽象數(shù)據(jù)類型至少

應(yīng)該包括放歌鍵、快進鍵、快退鍵和停止鍵；隨身聽的ADT描述為：

ADTRadio{

Data開始鍵begin

Data快進鍵kuaijin

Data快退鍵kuaitui

Data停止鍵stop

Operations

Constructor

Initialvalues:開始值，快進值，快退值，停止值

Process:將開始值賦給begin；將快進值賦給kuaijin；將快退值賦給kuaitui；

將停止值賦給stop；

Process:計算開始鍵的值

Output:返回開始鍵的值

KUAIJIN

Process:計算快進鍵的值

Output:返回快進鍵的值

KUAITUI

Process:計算快退鍵的值

Output:返回快退鍵的值

STOP

Process:計算停止鍵的值

Output:返回停止鍵的值

}//Radio

classRadio{

intbegin,kuaijin,kuaitui,stop;

Radio(intbeginO,intkuaijinO,intkuaituiO,intstopO)

{begin=beginO;kuaijin=kuaijinO;kuaitui=kuaituiO;stop=stopO;}

IntBEGIN(){returnbegin;}

IntKUAIJIN(){returnkuaijin;}

IntKUAITUI(){returnkuaitui;}

IntSTOP(){returnstop;}

};//Radio

1-5.試說明數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法三者之間的關(guān)系。

答案：1個數(shù)學模型可用多個不同的數(shù)據(jù)邏輯結(jié)構(gòu)表示；數(shù)據(jù)邏輯結(jié)構(gòu)是對數(shù)學模型的實現(xiàn)；

1個數(shù)據(jù)邏輯結(jié)構(gòu)可有多種不同的存儲結(jié)構(gòu)；存儲結(jié)構(gòu)是對邏輯結(jié)構(gòu)實現(xiàn)；算法是基于邏輯

結(jié)構(gòu)對操作的實現(xiàn)；函數(shù)是基于存儲結(jié)構(gòu)對算法的實現(xiàn)，是程序；

邏輯結(jié)構(gòu)直接影響到算法的效率，有時存儲結(jié)構(gòu)會影響到算法的基本操作及算法的實現(xiàn),

從而影響到算法的效率。設(shè)計與選擇合理的相互吻合的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)與算法是十分重

要的問題，也是我們學習本課程的目的之一。因此，設(shè)計選擇好的數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲

結(jié)構(gòu)和算法，既可以支持好的解決問題的方案，又可開發(fā)出好的程序。

1-6.請給出下列函數(shù)的大0和Q表示：

1-7.

100n+n2-2nVn,nlogn+2n=-n,Vn+log2n,Vnlogn2-5n

答案：

(1)0(n2)(2)0(nL5)(3)0(n,/2)(4)0(n,/2logn2)

1-8.設(shè)計一個算法判斷給定整數(shù)數(shù)組是否排好序。分析你的算法的時間復(fù)雜度。

intpanduan(inta[],intn){

if(a[0]<a[l]){

for(inti=l,i<n-l,i++){

if(a[i]<a[i+l])continue;

else{cout?！贝私o定整數(shù)數(shù)組沒有排好序”<<endl;

break;

)

)

cout?M此給定整數(shù)數(shù)組已經(jīng)排好序”<〈endl;

)

else{

for(inti=l,i<n-l,i++)

{if(a[i]>a[i+l])continue;

else{cout?>,此給定整數(shù)數(shù)組沒有排好序”。endl;

break;

)

}

cout<<”此給定整數(shù)數(shù)組已經(jīng)排好序”"endl;

答案:此算法的時間復(fù)雜度為：T(n)=0(n)

1-9.設(shè)計一個算法求整數(shù)集合中的最大數(shù)和最小數(shù)。分析你的算法的時間復(fù)雜度。

voidmaxmin(inta[n]){

intmax=a[0];

intmin=a[0];

for(inti=l;i<n;i++){

if(a[i]>max)

max=a[i];

if(a[i]<min)

min=a[i];

)

cout<X"此整數(shù)集合中的最大數(shù)為："<Xmax〈〈endl;

cout<<“此整數(shù)集合中的最小數(shù)為："<<min〈<endl;

}

答案:此算法的時間復(fù)雜度為:T(n)=0(2(n-l))=0(n)

1-10.設(shè)計一個排序算法，并分析你的算法的時間復(fù)雜度。

voidsort(inta[],intn){

intmin,t;

for(inti=0;i<n-l;i++){〃對數(shù)組進行交換排序

t=i;

for(intj=i+l;j<n;j++)〃尋找最小元素

if(x[j]<x[t])t=j;

if(t!=i)

{min=x[i];x[i]=x[t];x[t]=min;}

〃交換數(shù)組元素，將最小元素放入x[i]中

)

答案：此算法的時間復(fù)雜度為：T(n)=0(n?)

習題2

2-1.描述以下三個概念的區(qū)別：頭指針、頭結(jié)點、首結(jié)點(第一個元素結(jié)點)。在單鏈表中

設(shè)置頭結(jié)點的作用是什么？

答案：頭指針指向鏈表中第一個結(jié)點的存儲位置，在沒有頭結(jié)點的鏈表中，頭指針指向鏈表

中的首結(jié)點，

有頭結(jié)點的鏈表中，頭指針指向鏈表中的頭結(jié)點。

為了便于實現(xiàn)插入和刪除操作，可以在單鏈表的首結(jié)點之前增設(shè)一個結(jié)點，稱之為頭結(jié)

點。

2-3.用單鏈表表示兩個集合A和B,實現(xiàn)兩個集合的并操作A=AUB。

答案：voidList::Union(ListListLA,ListListLB,ListListLC){〃求并集

inty=LA.First();〃取LA中的第一個元素

while(y!=-l){

LC.Insert(y);〃從LA中取元素放到LC

y=LA.Next();}

intx=LB.First();

while(x!=-l){

intk=LA.Find(x);

if(k==-1)

LC.Insert(x);

x=LB.Next();

2-4.已知二維數(shù)組A…采用按行優(yōu)先順序存放，每個元素占K個存儲單元，并且第一個元素的

存儲地址為Loe?),請寫出求Loc(a”)的計算公式。如果采用列優(yōu)先順序存放呢？

答案:行優(yōu)先順序存放時Loc(aQ=Loc(an)+(i-l)*m*K+(j-l)*K

列優(yōu)先順序存放時LocLoc(ah)+(j-1)*m*K+(i-1)*K

2-5.在鏈表類的實現(xiàn)中增加一個成員函數(shù)實現(xiàn)對表中元素置逆的操作(設(shè)原鏈表為a。，ab

an-2)a?,;則置逆后的序列為a””a.,.2,a?a。)。對于有n個元素的線性表，你的算法的

運行時間應(yīng)為0(n)。

答案：算法描述：設(shè)head是頭指針，把鏈表中的每一個結(jié)點以頭插法插入到鏈表的第一個，

即可把把原鏈表的方向改過來，即置逆過來。且時間復(fù)雜度為0(n)。

Node*LinlList::invert(){

Node*p=head->next,*q;

head->next=NULL;

while(p){

q=p->next;

p->1ink=head->link;

head->link=p;

P=q；

}

returnhead;

2-6.請編寫26個字母按特定字母值插入或刪除的完整程序(表中的字母按從小到大的順序排

歹U),可自行選用順序存儲或鏈表結(jié)構(gòu)。

答案：voiddelete(chara){

charc[26];

for(inti=0;i<26;i++)

if(cLi]==a)

c[i]==，'；

}

2-7.用2.1.3中給出多項式定義及兩個多項式相加的算法思想，實現(xiàn)多項式類中AddPloyn

算法(先實現(xiàn)Create來創(chuàng)建多項式)。

答案：voidCreate(intn){

for(i=n;i>0;i--){

p=newNode();

if(p==NULL)exit;〃創(chuàng)建結(jié)點不成功，返回

cin>>p->coef;

cin?p->expn;

p->next=head->next;

head->next=p;

)

size=n;

}//Create

voidPolynList::AddPolyn(PolynListB){〃求兩多項式A(x)與B(x)的和

//qa和%分別指向A和B的首結(jié)點

PNode*qa=head;PNode*qb=B.head;

while(qa!=NULL&&qb!=NULL)

switch(compare(qa.expn,qb,.expn)){〃比較對應(yīng)項的指數(shù)

case,二':if(qa.coef+qb.coef!=0)qa.coef=qa.coef+qb.coef;

delete(qb.len());

elsedelete(qa.len());delete(qb.len());

qa=qa->next;qb=qb->next;break;

case，>，:floatcoef=GetElem(qb.len());

intexpn=GetElem(qb.len());

Insert(coef,expn,qa.len());

qb=qb->next;break;

case':qa=qa->next

)

while(qb!=NULL)

{qa->next=qb;

qb=qb->next;}

2-8.給出一個5X8的矩陣，其中正好有9個非0元素，并且在每一行和每一列中至少有一個

非0元素。對于這個稀疏矩陣，畫出其相應(yīng)的十字鏈表。

答案：

2-10.設(shè)計一個算法，將數(shù)組A(0..nT)中的元素循環(huán)右移k位，假設(shè)原數(shù)組序列為a。，ab

an-2,an-1;移動后的序列為4.k,…，E,a%…,an-k-l0要求只用一個元素大小

的附加存儲，元素移動或交換次數(shù)為0(n)。

答案：voidyouyi(inta[],intn,intk){

inti=0,m=0,p=a[n-k];

while(m<n)

{q=a[i];

a[i]=p;

i=(i+i*k)%n;

P=q；

m++;

}

)

2-11.已知主串s='ADBADABBAABADABBADADA',模式串pat='ADABBADADA'0寫出模式串的

nextval函數(shù)值，并由此畫出KMP算法匹配的全過程。

答案：模式串的nextval函數(shù)值為12,(具體過程略)

習題3

3-1.答案：

(1)輸出結(jié)果為：9

3

22

8

(2)換一道題

輸出結(jié)果為：Stack

3-2.答案：

(1)開出車站的順序有14種可能。所有可能的出棧序列為：

1,2,3,4

1,2,4,3

1,3,2,4

1,3,4,2

1,4,3,2

2,1,3,4

2,1,4,3

2,3,4,1

2,4,3,1

2,3,1,4

3,2,1,4

3,2,4,1

3,4,2,1

4,3,2,1

(2)

算法如下：

constintMaxStackSize=4;〃棧中能容納最大元素個數(shù)

classStack{

intStackList[MaxStackSize];

intpath[];〃存放輸出序列

inttop;

intcurp;〃標識path口中當前元素的位置

public:

Stack(){〃構(gòu)造函數(shù)，初始化一個空棧

StackList=newDataType[MaxStackSize];

top=-l;

}//Stack

boolIsEmpty(){〃判斷棧是否為空

if(top==-l)

returntrue;

else

returnfalse;

}//IsEmpty

boolIsFull(){〃判斷棧是否已滿

if(top==MaxStackSize-1)

returntrue;

else

returnfalse;

}//IsFull

voidPush(intx){〃入棧

StackList[++top]=x;

}//Push

intPop(){〃出棧

returnStackList[top-];

}//Pop

process(inttop,intpath口,intcurp)〃處理整數(shù)序列中top位置的元素

{intm,i,x;

if(top<MaxStackSize)〃編號top的元素x進棧時遞歸

{Push(x);//x進棧

process(top+1,path,curp);

Pop();〃出棧以恢復(fù)環(huán)境

)

if(!IsEmpty())〃編號top的元素x出棧時遞歸

{m=Pop();

path[curp]=m;〃將m輸出到path中

curp++;

process(top,path,curp);

Push(m);〃進棧以恢復(fù)環(huán)境

if(top>=MaxStackSize&&IsEmpty())〃輸出一種可能的方案

{for(i=0;i<curp;i++)

cout<<path[curp];

)

cout<<”?endl;

)

)

3-3.答案：

(1)GetHead[(a,b,c)]=(a)

(2)GetTai1[(a,b,c,d)]=(b,c,d)

(3)GetHead[((a,b),(c,d))]=(a,b)

(4)GetHead[GetTai1[((a,b),(c,d))]]=(c,d)

(5)GetTai1[GetHead[GetTai1[((a,b),(c.d))]]]=(d)

3-4.答案：

(1)頭尾表示法:

之，一旦元素出隊列時，front==rear時，需置tag為“0”，以便使下一次進行入隊列或出

隊列操作時，可由標志位tag的值來區(qū)別隊列當時的狀態(tài)是“滿”，還是“空”。

算法如下：

循環(huán)隊列中入隊算法如下：

voidEnter(DataTypeitem)〃帶tag域的循環(huán)隊列入隊算法

{if(front==rear&&tag==l)〃tag域的值為0表示空，1表示滿

return0;

rear=(rear+1)%MaxQSize;

SeqQueue[rear]=item;

if(front==rear)

tag=l；〃隊列滿

)

循環(huán)隊列中出隊算法如下：

DataTypeLeave()〃帶tag域的循環(huán)隊列出隊算法

{if(front==rear&&tag==0)〃tag域的值為0表示空，1表示滿

return0;

front=(front+l)%MaxQSize;

if(front==rear)

tag=0；〃隊空

returnSeqQueue[front];

)

這種算法因為不要預(yù)留一個空的存儲單元作為判斷隊滿的條件，因此在空間上能充分利用，

但在插入和刪除時每次都要檢查標志tag,同時在操作完成時，還要檢查頭、尾指針是否重

合，若是，則給tag重新賦值，故時間開銷多。故當隊中每個元素占用的空間較多時，還是

舍標志的方法較為適合。

3-6.答案：

(1)S1為空的條件是：topl=-l；

S2為空的條件是topl=MaxDualStackSiz2)

(2)S1和S2為滿的條件是：topl==top2T

(3)實現(xiàn)DualStack,其聲明如下。

constintMaxDualStackSize

classDualStack{

private:

inttopi,top2;

DataTypestackStorge[MaxDualStackSize];

public:

DualStack();

voidpush(DataTypeelt,intn);〃往棧n中壓入elt

if(topl==top2-l)〃棧滿

cout?w棧滿”

if(n==l)//elt入棧1

(

topl++;

stackStorge[topl]=elt;

)

if(n==2)〃elt入棧2

(

top2一;

stackStorge[top2]=elt;

)

)

DataTypePop(intn);〃從棧n中彈出元素

(

intx;

if(n==l)

{if(top==-l)

cout?w?？?！”《endl;

else

{x=stackStorge[topi];

topi一;}

￥

elseif(n==2)

{if(top2==MaxDualStackSize)

cout?>>?？?！"<<endl;

else

{x=stackStorge[top2];

top2++;

}

)

elsecout?w不存在該棧！"<<endl;

returnx;

}

DataTypeGetTop(intn);〃取棧n的頂元素

intx;

if(n==l)

{if(top==-l)

cout?"?？?！”?endl;

else

{x=stackStorge[topl];

)

}

elseif(n==2)

{if(top2==MaxDualStackSize)

cout?"?？?！"<<endl;

else

{x=stackStorge[top2];

}

elsecout<<”不存在該棧！”<<endl;

returnx;

)

boolStackEmpty(intn);〃棧n為空否

(

if(n==l)

return(topl==-l);

else

return(top2==MaxDualStackSize);

I

boolStackFull();〃棧n已滿否

(

returntop2==topl+l

)

voidClearStack(intn);//清空棧n

if(n==l)

topl=-l；

elseif(n==2)

top2=MaxDua1StackSize;

)

);

3-7.答案：

這里使用棧的一些堇本操作

push(st,x):>：元素x進棧st

pop(st,x)：出棧元素賦給x

IsEmpty(st)：判斷棧st是否為空

intEnter(stack&sl,stacks2,DataTypex)

(

if(sl->top==m-l)〃隊列上溢出

return0;

else

(

push(si,x);

return1;

)

)

intLeave(stack&sl,stacks2,DataTypex)

(

DataTypey;

while(!IsEmpty(si))〃將si的所有元素退棧后進入s2

(

pop(si,y);

push(s2,y);

)

pop(s2,x);〃將s2的棧頂元素退棧并賦給x

while(!IsEmpty(s2))〃將s2余下元素退棧后進入si中

(

pop(s2,y);

pushu(sl,y)：

3-8.答案:

算法如下：

voidHuiWen(LinkListL,intn)

{inti;

charch;

LinkList*p;snode*ls;

InitStack(Is);

p=L->next;

i=l；

while(i<=(n/2))〃將單鏈表中前半部分的字符進棧

(

ch=p->data;

Is.top++;

Is.data[ls.top]=ch;〃將ch送入棧頂指針所指向的單元

p=p->next;

i++；

)

if((n%2)==l)p=p->next;〃若n為奇數(shù)則中間位置的字符不進棧，p

指向〃單鏈表后半部分的第一個節(jié)點

k=l;〃設(shè)標志位k=l表示對應(yīng)字符全部相等，k=0表

〃示至少有一對字符不相等

while((p!=NULL)U(k==l))〃將棧1s中的字符彈出并逐個與單鏈表后半部

〃分的字符進行比較

(

ch=ls.data[Is.top-];〃將棧頂指針所指的單元內(nèi)的值賦給ch

if(p->data==ch)p=p->next〃若p指向的結(jié)點字符等于順序棧中棧頂指

針

〃字符，則p順鏈后移

elsek=0;〃若p指向的結(jié)點字符不等于順序棧中棧頂指

針

〃字符，則k=0

)

if(k)cout?w這串字符序列為“回文”<<endl;

elsecout<<”這串字符序列不為“回文”<<endl;

}

voidInitStach(Lstach&ls)

(

ls=(snode*)malloc(sizeof(snode));

Is.top=-l

)

3-9.答案：

算法如下：

intSPQDelete(seqPQueue*Q,DataType*x)〃把優(yōu)先級高的元素先刪除，刪除成功時

〃數(shù)返回1,否則返回0

DataTypemin=Q->list[0]〃初始選Q->list[0]為優(yōu)先級最高的元素

inti,minIndex=0;//minindex為優(yōu)先級最高元素的下標

if(Q->size<=0)

(

cout<<”隊列已空無數(shù)據(jù)元素可刪!"?endl;

return0;

)

for(i=l;i<Q->size;i++)〃尋找優(yōu)先級最高的元素及對應(yīng)下標

if(Q->list[i]<min)

(

min=Q->list[i];

minlndex=i;

}

*x=Q->list[minindex];

Q->list[minIndex]=Q->list[size-1];〃把最后一個元素放在被刪除元素的位

置

Q->size—;〃數(shù)據(jù)元素個數(shù)減1

return1;

}

3-10.答案：

算法如下：

intGetValue_NiBoLan(char*str)〃對逆波蘭式求值

{char*p；

snode*s;

p=str;

InitStack(s);〃s為操作數(shù)棧

while(*p)

(

if(*p是數(shù))

push(s,*p)；

else

(

pop(s,a);pop(s,b);

r=compute(b,*p,a)〃假設(shè)compute為執(zhí)行雙目運算的過程

push(s,r);

p++;

)

pop(s,r);

returnr;

3-11.答案：

voidGList_PrintElem(GListA,intlayer)〃遞歸輸出廣義表的原子及其所在層

次，layer表示當前層次

(

if(!A)return;

if(!A->tag)

cout?w原子為"所在層為"<<layer〈<endl;

else

(

GList_PrintElem(A->ptr.hp,layer+1);

GList_PrintElem(A->ptr.tp,layer);〃注意尾表與原表是同一層次

)

}//GList_PrintElem

3-12.答案：

voidGList_Copy(GListA,GList&B)〃復(fù)制廣義表的遞歸算法

(

if(!A->tag)〃當結(jié)點為原子時,直接復(fù)制

(

B->tag=0;

B->atom=A->atom;

)

else〃當結(jié)點為子表時

(

B->tag=l;

if(A->ptr.hp)

(

B->ptr.hp=malloc(sizeof(GLNode));

GList_Copy(A->ptr.hp,B->ptr.hp);

)〃復(fù)制表頭

if(A->ptr.tp)

(

B->ptr.tp=malloc(sizeof(GLNode));

GList_Copy(A->ptr.tp,B->ptr.tp);

〃復(fù)制表尾

}//GList_Copy

3-12.答案:

(1)

intMatch(charexp[],intn)

(

charst[MaxSize];

inttop=-l;

inti=0;

booltag=ture;

while(i<n&&tag==l)

(

if(exp[i]==>(9

{top++;

st[top]=epx[i];

)

if(exp[i]==,)9

if(st[top]二二'(')top一;

elsetag=ture;

i++；

if(top>=0)

tag=false;

return(tag);

習題4

4-1答案:

本書中主要結(jié)點的樹形表示可參考書中圖4.1的表示法，即全書為整棵樹的根，各個章

節(jié)為子樹，章節(jié)名又為子樹的根，各節(jié)為子樹，以此類推。

(1)樹中共有175個結(jié)點。

(2)葉結(jié)點即度為零的結(jié)點，在本書主要結(jié)點的樹形表示中為類似于1.1,1.2.1,1.2.2這

樣的結(jié)點。

(3)樹根的層次為1,其它任一結(jié)點所在的層是其雙親的層加lo故第三層結(jié)點是類似于

1.1,1.2,2.1,3.2這樣的結(jié)點。

(4)結(jié)點的度是樹的結(jié)點所擁有的子樹數(shù)。則根結(jié)點即全書節(jié)點擁有十棵子樹;分別為十

個章節(jié)，度為十。又如第一章有七節(jié)，即度為七。

4-3答案：

根據(jù)二叉樹的性質(zhì)得：有m個葉子的二叉樹最少有2m-1個節(jié)點。

4-4答案：

后序遍歷二叉樹結(jié)果為CBA,有五種二叉樹可得到這一結(jié)果，如圖：

4-5答案：

其參考算法如下：

voidSeqBiaoPreorder(inti){

if((i>last)||(!a[i])}return;

if(a[i])visit(a[i]);或cout〈〈a[i];/*訪問第i個節(jié)點*/

SeqBiaoPreorder(2*i+l);/*遞歸訪問第2i+l個節(jié)點*/

SeqBiaoPreorder(2*i+2);/*遞歸訪問第2i+2個節(jié)點*/

4-7擴充BinaryTree,增加Copy。操作，復(fù)制二叉樹。用兩種方法實現(xiàn)，第一種按前序遍歷

復(fù)制樹，第二種按后序遍歷復(fù)制樹。兩種實現(xiàn)方法所需要用到的遞歸棧空間有什么不同？

答案：第一種按前序遍歷復(fù)制樹參考算法：

voidCopy(BinTreeNode*rt){

if(rt){

BinTreeNode*temp=newBinTreeNode();

temp->data=rt->data;

temp->leftChild=Copy(rt->leftChild);

temp->rightChild=Copy(rt->rightChild);

)

}

第二種按后序遍歷復(fù)制樹參考算法：

voidBitree_Copy_Nonrecursive(BinaryTreeNode*T,BinaryTreeNode&U){

InitStack(SI);InitStack(S2);

SI.Push(T);

U=newBinaryTreeNode();

U->data=T->data;

q=U;S2.Push(U);

while(!StackEmpty(S)){

while(Gettop(SI,p)&&p){

q->1eftChi1d=newBinaryTreeNode();

q=q->leftChild;q->data=p->data;

push(SI,p->leftChild);

push(S2,q);

pop(SI,p);

pop(S2,q);

if(!StackEmpty(SI))

(

pop(SI,p);pop(S2,q);

q->rightChi1d=newBinaryTreeNode();

q=q->rightChild;q->data=p->data;

push(SI,p->rightChild);

push(S2,q);

4-8擴充BinaryTree,增加Compare(x)操作，對當前二叉樹與二叉樹x進行比較。若兩棵二

叉樹同構(gòu),則返回true,否則返回falseo

答案：參考算法如下：

boolequal(BinaryTreeNode*a,BinaryTreeNode*b){

if(!a&&!b)return1;

if(a&&b&&equal(a->leftChild,b->leftChild)&&equal(a->rightChild,

b->rightChild)return1;

return0;

|

4-10答案：

voidexchange(BinaryTreeNode*rt){

BinaryTreeNode*temp;

if(!rt->leftchild&&!lrt->rightchild)return;

else{temp=rt->leftChild;

rt->leftChild=rt->rightChild;

rt->rightChild=temp;

)

if(rt->leftChild)exchange(rt->leftChild);

if(rt->rightChild)exchange(rt->rightChiId);

4-12答案:

#include<iostream>

usingnamespacestd;

typedefenum{Link,hread}PointerTag;

typedefintTelemType;

typedefstructBiThrNode

(

TelemTypedata;

structBiThrNode*leftChild,*rightChild;

PointerTagItag,rtag;

}BiThrNode,*BiThrTree;

BiThrNode*pre;

voidInThreading(BiThrTreep)

(

if(p)

(

InThreading(p->leftChiId);

if(!p->leftChild)

(

p->1tag=hread;p->leftChild=pre;

)

if(!pre->rightChiId)

(

pre->rtag=hread;pre->rightChild=p;

}

pre=p;

InThreading(p->rightChiId);

}

)

intInorderThreading(BiThrTree&Thrt,BiThrTreeT)

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrTree))))

exit(1);

Thrt->1tag=Link;

Thrt->rtag=hread;

Thrt->rightChild=Thrt;

if(!T)

(

Thrt->leftChild=Thrt;

i

else

(

Thrt->leftChild=T;

pre=Thrt;

InThreading(T);

pre->rightChild=Thrt;pre->rtag=hread;

Thrt->rightChild=pre;

I

return1;

}

intmain()

(

return0;

)

4-14答案：

樹與二叉樹的轉(zhuǎn)換可參考本書4.4節(jié)樹與二叉樹的轉(zhuǎn)換算法進行。

4-15已知一棵二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，編寫完成下列操作的算法：對于樹中每一個

元素值為x的結(jié)點，刪去以它為根的子樹，并釋放相應(yīng)的結(jié)點。

答案：

voidDel_Sub_x(BinaryTreeNode*T,intx){/*刪除所有以元素x為根的子樹*/

if(T->data==x)Del_Sub(T);/*刪除該子樹*/

else{/*在左右子樹中繼續(xù)查找*/

if(T->leftChild)Del_Sub_x(T->leftChiId,x);

if(T->rightChiId)Del_Sub_x(T->rightChiId,x);

}/*else*/

}/*Del_Sub_x*/

voidDel_Sub(BitreeT){/*刪除子樹T*/

if(T->leftChiId)Del_Sub(T->leftChild);

if(T->rightChild)Del_Sub(T->rightChi1d);

free⑴；

}/*Del_Sub*/

4-16答案：

voidPrint_CSTree(CSNode*T,inti){

/*按凹入表形式打印輸出樹的元素，i表示結(jié)點所在層次,初次調(diào)用時i=l*/

if(!T)return;

for(j=l;j<i;j++)cout?'';

cout<<T->data<<endl;

Print_CSTree(T->firstChiId,i+1);

Print_CSTree(T->nextSibling,i+1);

I

4.17對以下存儲結(jié)構(gòu)分別寫出計算樹的深度的算法。

(1)雙親表示法；(2)子女兄弟表示法。

答案：(1)雙親表示法計算樹的深度的算法參考答案：

intGetDepth_CSTree(CSNode*T){/*求雙親表表示的樹T的深度*/

maxdep=l;

for(i=0;i<n,i++){

for(j=i,dep=l;(j=T.nodes[j].parent)>-l;dep++);/*求每一個結(jié)點的深度*/

if(dep>maxdep)maxdep=dep;

returnmaxdep;

}/*GetDepth_CSTree*/

(2)子女-兄弟表示法計算樹的深度的算法參考答案：

intGetDepth_CSTree(CSNode*T){/*求子女-兄弟表示的樹A的深度*/

if(!T)return0;

elsereturn1+Max(Depth(T->firstChiId),Depth(T->nextSibling));

}/*GetDepthCSTree*/

習題5

5-1.答案：

實現(xiàn)一個簡單的文檔檢索管理系統(tǒng)。它將文檔(摘要引用)插入到系統(tǒng)中，建立關(guān)鍵字與

文檔之間的關(guān)

聯(lián)，并按照給定的關(guān)鍵字檢索文檔。

ADTDocumentSystem{

Stringkey;〃關(guān)鍵字

Documentdocument;〃文當摘要

DocumnetSystemsystem;

)

ADTDocument{

Stringpreface;〃摘要

Stringcontent;〃弓|用

)

voidinsertDocumentSystem(DcoumentSystemsys,Document,doc){

sys.system=newDocuemntSystem(key,doc);

}

Documentsearch(key,system){

While(system->sys!=nul1){

If(system->key==key)

Returnsystem->doc;

Elsesystem=system->sys;

)

)

5-2.答案：

設(shè)計一個算法FreqCount,實現(xiàn)頻率計數(shù)自組織線性查找表啟發(fā)式規(guī)則，假定線性查找表使

用數(shù)組實現(xiàn)。它把查找的值作為輸入，并且相應(yīng)地調(diào)整線性查找表。如果值不在線性查

找表中，就把它添加到線性查找表的最后，其頻率計數(shù)是1。

使用到的數(shù)據(jù)類型：采用二維數(shù)組實現(xiàn)：

IntLink[2][n]〃申明一個2行n列的數(shù)組

Intcounter=0〃標記在Link中此時存在多少個值

VoidinitLink(intlocation){

For(inti=0;i<=location;i++)

從i到location之間的值按頻率從大到小排列

)

Booleansearch(intnumber){

for(inti=0;i<counter;i++){

If(Link[i][0]==number){

Link[i][1]++;

initLink(i);〃〃如果找到后則重新使數(shù)組按Link[l]口從大到小

排列

Returntrue;

)

}

Link[0][counter]=number;

Link[l][counter++]=l;

Returnfalse;

}

5-3.答案：

設(shè)計一個算法Transpose,實現(xiàn)轉(zhuǎn)置自組織線性查找表啟發(fā)式規(guī)則，假定線性查找表使

用數(shù)組實現(xiàn)。它把查找的值作為輸入，并且相應(yīng)地調(diào)整線性查找表。如果值不在線性查

找表中，就把它添加到線性查找表的最后。

使用到的數(shù)據(jù)類型：采用二維數(shù)組實現(xiàn)：

IntLink[n]//申明一個2行n列的數(shù)組

Intcounter=0〃標記在Link中此時存在多少個值

Booleansearch(intnumber){

for(inti=0;i<counter;i++){

If(Link[i]==number){

If(i>0)

交換Link[i]與Link-；〃轉(zhuǎn)換位置

Returntrue;

)

Link[counter++]=number;

Returnfalse;

)

5-4.答案:

對順序存儲的有序查找表：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,用二分

查找算法查找關(guān)鍵字2、10、17時，其比較次數(shù)分別是多少？

先看key=2的查找過程：

位置：01234567891011121314

(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

第一次：tlow=0tmid=7fhigh=14

第二次：tlow=0tmid=3thigh=6

第三次:tlow=0tmid=lthigh=2

成功結(jié)束!

再看key=10的查找過程：

位置：01234567891011121314

(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

第一次：tlow=0tmid=7fhigh=14

第二次：tlow=8tmid=llthigh=14

第三次:tlow=8tmid=9thigh=10

成功結(jié)束!

再看key=17的查找過程：

位置：01234567891011121314

(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

第一次：tlow=0tmid=7fhigh=14

第二次：tlow=8tmid=llthigh=14

第三次：tlow=12fmid=13thigh=14

第四次

tlow=14thigh=14

第五次查找失敗!

5-5.答案：

對表：Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec

(1)試按表中元素的順序依次插入到一棵初始為空的二叉查找樹中；畫出插入完成后的

二叉查找樹.，并求其在等概率情況下查找成功的平均查找長度。

(2)若對表中元素先進行排序構(gòu)成有序表，在等概率情況下對此表進行二分查找，試求

成功查找的平均查找長度。

5-6.答案：

假設(shè)在某語言中，可通過語句EQUIVALENCE定義共享變量，共享變量共享同一存儲單元。其

規(guī)則是EQUIVALENCE語句中的每一對括號內(nèi)的變量是共享變量，含共同變量的組內(nèi)的所

有變量也是共享變量。如EQUIVALENCE((a,c,f),(h,k,m),(x,d,a),(k,e),(d,j,p,s)),

定義了a、c、f、x、d、_j、p、s是共享變量，h、k、m、e是共享變量，這樣僅需為這

些變量分配兩個存儲單元即可。試借助MFSet,以EQUIVALENCE語句為輸入，計算所需

單元數(shù)。

classMFSet{

intn;

int*parent;〃下標對應(yīng)成員，值為雙親，根兼作子集的名稱，根的雙親置0

public:

MFSet(intm)

viodMerge(inta,intb);//a和b為根,即子集名

intFind(inte);

voidOut();

};//classMFSet

MFSet(intm){//初始時，共輸入m個字符,初始時為

n=m;parent=newint[n+1];

for(i=l;i<=n;i++)parent[i]=-l;//parent[0]暫且空閑

:}

viodMerge(chara,charb){〃&和b為根，即集合名

parent[b-'a']=a-'a';

boolFind(chare){

inta=e-'a';

while(parent[a]!=-l){

if(parent[])

a=parent[a];

returnfalse;

}//Find

5-7.答案:

在0?16的散列地址空間中，試對關(guān)鍵字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,

Sep,Oct,Nov,Dec),分別用以下兩種方法構(gòu)造哈希表，假設(shè)h(key)=|_i/2」，其中i為

關(guān)鍵字中第一個字母在字母表中的序號：(1)用線性探測再散列；(2)用開哈希法處理。

(1)用線性探測再散列：

01234567891011121314151()

apraugfebdecjanjulmarmarnovoctsep

(2)用開哈希法處理(略)

5-8.答案：

采用線性探測再散列，在下列各種情況下找到哈希函數(shù)除數(shù)m的合適值。

(1)n=50,S?W3,UnW20。(2)n=500,SnW5,UnW60。(3)n=10,S?W2,Un<10。

(1)S=l/2(l+l/(l-a))<=3U=l/2(1+1/(1-a)(1-a))<=3

可知a<0.9;由S知a<=4/5;即a<=min(0.9,0.8);

其中a=n/m;因為n=50;所以250/4的上限，所以m取63。

(2)(3)做法同上。

5-9.答案：

對于以下各種條件，找出哈希函數(shù)除數(shù)m