《算法與數據結構》習題集及答案

習題1

1-1.數據的邏輯結構為：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>}

請畫出它的結構圖。它是線性結構嗎？哪些結點是開始結點？哪些結點是終端結點？

答案：

它不是線性結構，a結點是開始結點，f結點是終端結點。

1-2.試說明基本數據類型、數據結構和抽象數據類型的聯系與差異。

答案：

數據結構所研究內容的著重點主要體現在三個方面：

第一是數據間的邏輯關系，即數據元素之間的關系。

第二是數據的存儲關系，即數據在計算機中的存儲結構。

第三是算法，即定義在數據對象上的操作的實現策略，是對操作的描述。

因此，簡單說來，數據結構所研究的問題是如何將現實世界中的事物合理描述為計算機

世界中所研究的對象，并根據研究對象的特點，分析對象之間的關系、存儲結構和操作的學

科。

基本數據類型（DataType）：數據是按照數據結構分類的，具有相同數據結構的數據

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

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

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

（浮點型）和char（字符型），有構造類型數組、結構、聯合、指針、枚舉型和自定義等。

抽象數據類型即不論其內部結構如何變化，只要數學特性不變，都不影響抽象數據類型

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

決于抽象數據類型的邏輯特性，與它在計算機內部如何表示和實現無關。

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

答案：引入抽象數據類型的目的是把數據類型的表示和數據類型上運算的實現與這些數據類

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

抽象數據類型的定義僅取決于抽象數據類型的邏輯特性，與它在計算機內部如何表示和實現

無關，即不論其內部結構如何變化，只要數學特性不變，都不影響抽象數據類型外部的使用。

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

答案：

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

應該包括放歌鍵、快進鍵、快退鍵和停止鍵；隨身聽的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.試說明數據的邏輯結構、存儲結構和算法三者之間的關系。

答案：1個數學模型可用多個不同的數據邏輯結構表示；數據邏輯結構是對數學模型的實現；

1個數據邏輯結構可有多種不同的存儲結構；存儲結構是對邏輯結構實現；算法是基于邏輯

結構對操作的實現；函數是基于存儲結構對算法的實現，是程序；

邏輯結構直接影響到算法的效率，有時存儲結構會影響到算法的基本操作及算法的實現,

從而影響到算法的效率。設計與選擇合理的相互吻合的邏輯結構、存儲結構與算法是十分重

要的問題，也是我們學習本課程的目的之一。因此，設計選擇好的數據邏輯結構、數據存儲

結構和算法，既可以支持好的解決問題的方案，又可開發出好的程序。

1-6.請給出下列函數的大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.設計一個算法判斷給定整數數組是否排好序。分析你的算法的時間復雜度。

intpanduan(inta[],intn){

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

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

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

else{cout。”此給定整數數組沒有排好序”<<endl;

break;

)

)

cout?M此給定整數數組已經排好序”<〈endl;

)

else{

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

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

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

break;

)

}

cout<<”此給定整數數組已經排好序”"endl;

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

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

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"此整數集合中的最大數為："<Xmax〈〈endl;

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

}

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

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

voidsort(inta[],intn){

intmin,t;

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

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;}

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

)

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

習題2

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

設置頭結點的作用是什么？

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

中的首結點，

有頭結點的鏈表中，頭指針指向鏈表中的頭結點。

為了便于實現插入和刪除操作，可以在單鏈表的首結點之前增設一個結點，稱之為頭結

點。

2-3.用單鏈表表示兩個集合A和B,實現兩個集合的并操作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.已知二維數組A…采用按行優先順序存放，每個元素占K個存儲單元，并且第一個元素的

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

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

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

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

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

運行時間應為0(n)。

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

即可把把原鏈表的方向改過來，即置逆過來。且時間復雜度為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),可自行選用順序存儲或鏈表結構。

答案：voiddelete(chara){

charc[26];

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

if(cLi]==a)

c[i]==，'；

}

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

算法(先實現Create來創建多項式)。

答案：voidCreate(intn){

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

p=newNode();

if(p==NULL)exit;〃創建結點不成功，返回

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的首結點

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

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

switch(compare(qa.expn,qb,.expn)){〃比較對應項的指數

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元素。對于這個稀疏矩陣，畫出其相應的十字鏈表。

答案：

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

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

的附加存儲，元素移動或交換次數為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函數值，并由此畫出KMP算法匹配的全過程。

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

習題3

3-1.答案：

(1)輸出結果為：9

3

22

8

(2)換一道題

輸出結果為：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;〃棧中能容納最大元素個數

classStack{

intStackList[MaxStackSize];

intpath[];〃存放輸出序列

inttop;

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

public:

Stack(){〃構造函數，初始化一個空棧

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)〃處理整數序列中top位置的元素

{intm,i,x;

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

{Push(x);//x進棧

process(top+1,path,curp);

Pop();〃出棧以恢復環境

)

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

{m=Pop();

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

curp++;

process(top,path,curp);

Push(m);〃進棧以恢復環境

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的值來區別隊列當時的狀態是“滿”，還是“空”。

算法如下：

循環隊列中入隊算法如下：

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

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

return0;

rear=(rear+1)%MaxQSize;

SeqQueue[rear]=item;

if(front==rear)

tag=l；〃隊列滿

)

循環隊列中出隊算法如下：

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

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

return0;

front=(front+l)%MaxQSize;

if(front==rear)

tag=0；〃隊空

returnSeqQueue[front];

)

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

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

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

舍標志的方法較為適合。

3-6.答案：

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

S2為空的條件是topl=MaxDualStackSiz2)

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

(3)實現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為奇數則中間位置的字符不進棧，p

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

k=l;〃設標志位k=l表示對應字符全部相等，k=0表

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

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

〃分的字符進行比較

(

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

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

針

〃字符，則p順鏈后移

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

針

〃字符，則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)〃把優先級高的元素先刪除，刪除成功時

〃數返回1,否則返回0

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

inti,minIndex=0;//minindex為優先級最高元素的下標

if(Q->size<=0)

(

cout<<”隊列已空無數據元素可刪!"?endl;

return0;

)

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

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

(

min=Q->list[i];

minlndex=i;

}

*x=Q->list[minindex];

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

置

Q->size—;〃數據元素個數減1

return1;

}

3-10.答案：

算法如下：

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

{char*p；

snode*s;

p=str;

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

while(*p)

(

if(*p是數)

push(s,*p)；

else

(

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

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

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)〃復制廣義表的遞歸算法

(

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

(

B->tag=0;

B->atom=A->atom;

)

else〃當結點為子表時

(

B->tag=l;

if(A->ptr.hp)

(

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

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

)〃復制表頭

if(A->ptr.tp)

(

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

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

〃復制表尾

}//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答案:

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

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

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

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

樣的結點。

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

1.1,1.2,2.1,3.2這樣的結點。

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

個章節，度為十。又如第一章有七節，即度為七。

4-3答案：

根據二叉樹的性質得：有m個葉子的二叉樹最少有2m-1個節點。

4-4答案：

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

4-5答案：

其參考算法如下：

voidSeqBiaoPreorder(inti){

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

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

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

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

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

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

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

voidCopy(BinTreeNode*rt){

if(rt){

BinTreeNode*temp=newBinTreeNode();

temp->data=rt->data;

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

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

)

}

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

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進行比較。若兩棵二

叉樹同構,則返回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答案：

樹與二叉樹的轉換可參考本書4.4節樹與二叉樹的轉換算法進行。

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

元素值為x的結點，刪去以它為根的子樹，并釋放相應的結點。

答案：

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

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

else{/*在左右子樹中繼續查找*/

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表示結點所在層次,初次調用時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對以下存儲結構分別寫出計算樹的深度的算法。

(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++);/*求每一個結點的深度*/

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.答案：

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

文檔之間的關

聯，并按照給定的關鍵字檢索文檔。

ADTDocumentSystem{

Stringkey;〃關鍵字

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.答案：

設計一個算法FreqCount,實現頻率計數自組織線性查找表啟發式規則，假定線性查找表使

用數組實現。它把查找的值作為輸入，并且相應地調整線性查找表。如果值不在線性查

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

使用到的數據類型：采用二維數組實現：

IntLink[2][n]〃申明一個2行n列的數組

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);〃〃如果找到后則重新使數組按Link[l]口從大到小

排列

Returntrue;

)

}

Link[0][counter]=number;

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

Returnfalse;

}

5-3.答案：

設計一個算法Transpose,實現轉置自組織線性查找表啟發式規則，假定線性查找表使

用數組實現。它把查找的值作為輸入，并且相應地調整線性查找表。如果值不在線性查

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

使用到的數據類型：采用二維數組實現：

IntLink[n]//申明一個2行n列的數組

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

Booleansearch(intnumber){

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

If(Link[i]==number){

If(i>0)

交換Link[i]與Link-；〃轉換位置

Returntrue;

)

Link[counter++]=number;

Returnfalse;

)

5-4.答案:

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

查找算法查找關鍵字2、10、17時，其比較次數分別是多少？

先看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

成功結束!

再看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

成功結束!

再看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)若對表中元素先進行排序構成有序表，在等概率情況下對此表進行二分查找，試求

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

5-6.答案：

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

規則是EQUIVALENCE語句中的每一對括號內的變量是共享變量，含共同變量的組內的所

有變量也是共享變量。如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語句為輸入，計算所需

單元數。

classMFSet{

intn;

int*parent;〃下標對應成員，值為雙親，根兼作子集的名稱，根的雙親置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的散列地址空間中，試對關鍵字序列(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,

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

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

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

01234567891011121314151()

apraugfebdecjanjulmarmarnovoctsep

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

5-8.答案：

采用線性探測再散列，在下列各種情況下找到哈希函數除數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.答案：

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