數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言描述）習(xí)題及答案（羅福強(qiáng)）第1-5章

數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言描述）習(xí)題及答案

1.5習(xí)題

填空題

1.數(shù)據(jù)的物理結(jié)構(gòu)包括順序結(jié)構(gòu)的表示和存儲(chǔ)和鏈?zhǔn)浇Y(jié)構(gòu)的表示和存儲(chǔ)。

2.對(duì)于給定的n個(gè)元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有（集合結(jié)構(gòu)），（線(xiàn)性結(jié)構(gòu)），（樹(shù)

型結(jié)構(gòu)），（圖型結(jié)構(gòu)）四種。

3.一個(gè)算法具有5個(gè)特性：（有窮性）、（確定性）、（可行性），有零個(gè)或多個(gè)

輸入、有一個(gè)或多個(gè)輸出。

4.抽象數(shù)據(jù)類(lèi)型被形式地定義為（D,S,P）,其中D是（數(shù)據(jù)元素）的有限

集合，S是D上的（關(guān)系）有限集合，P是對(duì)D的（基本操作）集合。

5.數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)的（邏輯結(jié)構(gòu)）、數(shù)據(jù)的（存儲(chǔ)結(jié)構(gòu)）和數(shù)據(jù)的（操

作）這三個(gè)方面的內(nèi)容。

6.一個(gè)算法的效率可分為（時(shí)間）效率和（空間）效率。

二.單項(xiàng)選擇題

1.線(xiàn)性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（D）。

A.一對(duì)多關(guān)系B.多對(duì)多關(guān)系C.多對(duì)一關(guān)系D.一對(duì)一關(guān)系

2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（C）結(jié)構(gòu)。

A.存儲(chǔ)B.物理C.邏輯D.物理和存儲(chǔ)

3.算法分析的目的是（B）。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.分析算法的效率以求改進(jìn)

C.研究算法中的輸入和輸出的關(guān)系D.分析算法的易懂性和文檔性

4.算法分析的兩個(gè)主要方面是（A）。

A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)明性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

5.計(jì)算機(jī)算法指的是（C）。

A.計(jì)算方法B.排序方法

C.解決問(wèn)題的有限運(yùn)算序列D.調(diào)度方法

6.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（A）。

1

A.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

三.計(jì)算題

1.計(jì)算機(jī)執(zhí)行下面的語(yǔ)句時(shí)，語(yǔ)句s的執(zhí)行次數(shù)為（（n-2）（n+3）/2）。

for（i=l；i<n-l；i++）

for（j=n;j>=i;j-）

2.在有n個(gè)選手參加的單循環(huán)賽中，總共將進(jìn)行（n（n-l）/2）場(chǎng)比賽。

3.試給出下面兩個(gè)算法的時(shí)間復(fù)雜度。

（1）for（i=l；i<=n；i++）0（n）

x=x+l;

（2）for（i=l；i<=n；i++）0（n2）

for（j=l；j<=n；j++）

x=x+l;

2.4習(xí)題

一.填空題

1.線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)分別為（順序存儲(chǔ)）和（鏈?zhǔn)酱鎯?chǔ)）。

2.順序表中，邏輯上相鄰的元素，其物理位置一一定相鄰。在單鏈表中，

邏輯上相鄰的元素，其物理位置不一定相鄰。

3.若經(jīng)常需要對(duì)線(xiàn)性表進(jìn)行插入和刪除操作，則最好采用（鏈?zhǔn)剑┐鎯?chǔ)結(jié)

構(gòu)，若線(xiàn)性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求

以最快的速度存取線(xiàn)性表中的元素，則最好采用（順序）存儲(chǔ)結(jié)構(gòu)。

4.在順序表中等概率下插入或刪除一個(gè)元素，需要平均移動(dòng)（n/2）元素，具體

移動(dòng)的元素個(gè)數(shù)與（插入或刪除位置）有關(guān)。

5.在帶頭結(jié)點(diǎn)的非空單鏈表中，頭結(jié)點(diǎn)的存儲(chǔ)位置由（head頭指針）指示，首

元素結(jié)點(diǎn)的存儲(chǔ)位置由（head.next）指示，除首元素結(jié)點(diǎn)外，其它任一元

素結(jié)點(diǎn)的存儲(chǔ)位置由（其直接前驅(qū)）指示。

6.已知L是帶頭結(jié)點(diǎn)的單鏈表，且p結(jié)點(diǎn)既不是首元素結(jié)點(diǎn)，也不是尾元素

結(jié)點(diǎn)。按要求從下列語(yǔ)句中選擇合適的語(yǔ)句序列。

a.在p結(jié)點(diǎn)后插入s結(jié)點(diǎn)的語(yǔ)句序列是：o

s.next=p.next;p.next=s;

b.在p結(jié)點(diǎn)前插入s結(jié)點(diǎn)的語(yǔ)句序列是：o

2

q=head;while(q.next!=p)q=q.next;s.next=p;q.next=s;

C.在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是：0

s.next=head.next;head.next=s;

d.在表尾插入s結(jié)點(diǎn)的語(yǔ)句序列是：o

while(p.next!=null)p=p.next;s.next=null;p.next=s;

二.單項(xiàng)選擇題

1.線(xiàn)性表是(A)。

A.一個(gè)有限序列，可以為空B.一個(gè)有限序列，不能為空

C.一個(gè)無(wú)限序列，可以為空D.一個(gè)無(wú)限序列，不能為空

2.帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是(B)。

A.head==nullB.head,next==null

C.head.next==LD.head!=null

3.在表長(zhǎng)為n的單鏈表中，算法時(shí)間復(fù)雜度為0(n)的操作為(D)。

A.刪除p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)B.在p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)

C.刪除表中第一個(gè)結(jié)點(diǎn)D.查找單鏈表中第i個(gè)結(jié)點(diǎn)

4.在表長(zhǎng)為n的順序表中，算法時(shí)間復(fù)雜度為0(1)的操作為(C)。

A.在第i個(gè)元素前插入一個(gè)元素B.刪除第i個(gè)元素

C.在表尾插入一個(gè)元素D.查找其值與給定值相等的一個(gè)元素

5.設(shè)單鏈表中指針p指向結(jié)點(diǎn)ai,若要?jiǎng)h除ai之后的結(jié)點(diǎn)，則需修改指針的

操作為(B)。

A.p=p.nextB.p.next=p.next.next

C.p=p.next.nextD.next=p

三.綜合題

1.試比較線(xiàn)性表的兩種存儲(chǔ)結(jié)構(gòu)各自的優(yōu)缺點(diǎn)。

順序存儲(chǔ)：

優(yōu)點(diǎn)：存儲(chǔ)密度大，存儲(chǔ)空間利用率高，可隨機(jī)存取。

缺點(diǎn)：插入或刪除元素時(shí)不方便。

鏈?zhǔn)酱鎯?chǔ)：

優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活。

結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；

缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低，非隨機(jī)存取。

2.設(shè)線(xiàn)性表存于數(shù)組a[0..n-l]的前R個(gè)分量中，且遞增有序，試寫(xiě)一算法，

將x插入到線(xiàn)性表的適當(dāng)位置上，以保持線(xiàn)性表的有序性。

publicvoidsortOrder(Tx){

inti=0,j;

3

while(i<length)

if(((Comparable)x).compareTo(listArray[i])>=0)

i++;

else{

for(j=length-1；j>=i;j-)

listArray[j+1]=listArray[j];

listArray[i]=x;

length++;

break;

3.試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線(xiàn)性表的就地逆置算法，即在原表的存儲(chǔ)空

間將線(xiàn)性表(al,a2,an)逆置為(an,an-1,al)o

就地逆置：(al,a2,...,an)逆置為(an,...,a2,al)

publicvoidinverse(){

inti=0,j;

Ttemp;

for(j=length-l;i<=j;i++,j-){

temp=listArrayfi];

listArray[i]=listArray[j];

listArray[j]=temp;

)

)

〃先將L的頭節(jié)點(diǎn)head的Next域置為NULL變成一個(gè)空鏈表，然后用p結(jié)點(diǎn)

采用頭插法插入到L中。

publicvoidinverse(){

if(head!=null||head.next!=null){

Node<T>p=head.next;

head.next=null;

Node<T>q=null;

while(p!=null){

q=p;

p二p.next;

q.next=head.next;

head.next=q;

4.試編寫(xiě)在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)最小值結(jié)點(diǎn)的算法。

publicvoiddelMin()

{

Node<T>p=head,q=head.next,p1=null,q1=null;

if(!isEmpty()){

Tmin=q.data;

while(q!=null){

if(((Comparable)min).compareTo(q.data)>0){

min=q.data;

pl=p;

ql=q;

4

p=q；

q=q.next;

)

pl.next=ql.next;

}

Length—;

)

5.設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next三個(gè)域外，還有一個(gè)

訪問(wèn)頻度域freq,在鏈表被起用之前，其值均初始化為零。每當(dāng)對(duì)鏈表進(jìn)

行一次LocateNode(L,x)運(yùn)算，便令元素值為x的結(jié)點(diǎn)的freq域的值加1,

并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問(wèn)頻度的遞減序排列，以便使頻繁訪問(wèn)

的結(jié)點(diǎn)總是靠近表頭。試寫(xiě)一個(gè)符合上述要求的算法LocateNode(L,x)o

static<TextendsComparable>booleanLocateNode(dlinklistL,Tx){

DuNode<T>p=L.getHead().next;

〃指針p用于查找第一個(gè)data域等于x的結(jié)點(diǎn)

DuNode<T>q;

while(p!=null&&(p.data).equals(x)==false)

p=p.next;

if(p=null)//p為空，意味著沒(méi)有找到data域等于x的結(jié)點(diǎn)

returnfalse;

else{

p.freq++;//將找到的data域等于x的結(jié)點(diǎn)的訪問(wèn)頻度值加1

q=p.prior;

//指針q用于查找p的前面結(jié)點(diǎn)中第一個(gè)freq域不小于當(dāng)前p所指

結(jié)點(diǎn)的freq域的結(jié)點(diǎn)

while(q!=L.getHead()&&(q.freq).compareTo(p.freq)<0))

q=q.prior;

if(q!=p.prior){〃如果q發(fā)生了前移，才有必要移動(dòng)p

p.prior.next=p.next;

if(p.next!=null){

p.next.prior=p.prior;

〃如果p不是終端結(jié)點(diǎn)，才有必要修改p的后繼結(jié)點(diǎn)的

prior域

p.prior=q;

p.next=q.next;

q.next=p;

p.next.prior=p;//將p插入到q的后邊

returntrue;

6.一個(gè)單循環(huán)鏈表F,每個(gè)結(jié)點(diǎn)包含三個(gè)域：pre>data和next,其中pre為

null,將其變?yōu)殡p循環(huán)鏈表的算法如下，請(qǐng)對(duì)算法中的空白處填空：

intdouble_list(DuLinkListF)

5

DuLNode*p,*q;

if(F.next==F)

{F.pre二F;return;}/*循環(huán)鏈表為空的情況*/

q=F;p=F.next;

while(p!=q)

{

p.pre=q;

q=_B____；

p=p.next;

}/*while*/

p.pre=q;

return0;

3.4習(xí)題

一.單項(xiàng)選擇題

1.一個(gè)棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是_C_o

A.edcbaB.decbaC.dceabD.abcde

2.若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間top[i]代表第i個(gè)棧

(i=l,2)棧頂，棧1的底在v[l],棧2的底在V[m],則棧滿(mǎn)的條件是

(B)o

A.top[2]-top[l]|=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.topfl]=top[2]

3.若已知一個(gè)棧的入棧序列是1,2,3,…，n,其輸出序列為pl,p2,

p3,...?pn,若pl=n,則pi為_(kāi)C_。

A.iB.n=iC.n-i+1D.不確定

4.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是_A_。

A.順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.散列方式和索引方式

C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D.線(xiàn)性存儲(chǔ)結(jié)構(gòu)和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)

5.判定一個(gè)棧ST(最多元素為m0)為空的條件是_B_。

A.ST.top!=-1B.ST.top==-1

C.ST.top!=mO-1D.ST.top==mO-1

6.判定一個(gè)棧ST(最多元素為mO)為棧滿(mǎn)的條件是_D_。

A.ST.top!=-1B.ST.top==-1

C.ST.top!=mO-1D.ST.top==mO-1

7.棧的特點(diǎn)是_B—,隊(duì)列的特點(diǎn)是_A_o

A.先進(jìn)先出B.先進(jìn)后出

8.一個(gè)隊(duì)列的入列序列是1,2,3,4,則隊(duì)列的輸出序列是_B_。

A.4,3,2,1B.1,2,3,4

6

C.1,4,3,2D.3,2,4,1

9.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為mO）為空的條件是_A_o

A.front==rearB.front!=rear

C.front==（rear+1）%m0D.front!=（rear+1）%m0

10.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為mO）為滿(mǎn)隊(duì)列的條件是_C_o

A.front==rearB.front!=rear

C.front==（rear+1）%m0D.front!=（rear+1）%m0

11.循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值，已知其頭尾指針?lè)謩e是front和

rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是_A_。

A.（rear-front+m）%mB.rear-front+1

C.rear-front-1D.rear-front

12.棧和隊(duì)列的共同點(diǎn)是_C_o

A.都是先進(jìn)后出B.都是先進(jìn)先出

C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)

13.向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行_C_。（不帶

空的頭結(jié)點(diǎn)）

A.HS.next=s;B.s.next=HS.next;HS.next=s;

C.s.next=HS;HS=s;D.s.next=HS;HS=HS.next;

14.從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，

則執(zhí)行_D_。（不帶空的頭結(jié)點(diǎn)）

A.x=HS;HS=HS.next;B.x=HS.data;

C.HS=HS.next;x=HS.data;D.x=HS.data;HS=HS.next;

二.填空題

1.向棧中壓入元素的操作是（先移動(dòng)棧頂指針，后存入元素）。

2.對(duì)棧進(jìn)行退棧時(shí)的操作是（先取出數(shù)據(jù)元素，后移動(dòng)棧頂指針）。

3.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（前一個(gè)位置）。

4.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是（先移動(dòng)隊(duì)首指針，后取出元

素）。

5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿(mǎn)時(shí)共有（n-1）個(gè)元素。

6.一個(gè)棧的輸入序列是12345,則棧的輸出序列43512是（不可能的）。

7.一個(gè)棧的輸入序列是12345,則棧的輸出序列12345是（可能的）。

8.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是（HS==null）。

三.算法設(shè)計(jì)題：

1.設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫(xiě)一算法，將x插入到順序表的適

當(dāng)位置上，以保持該表的有序性。

2.試寫(xiě)一算法，實(shí)現(xiàn)順序表的就地逆置，即利用原表的存儲(chǔ)空間將線(xiàn)性表

（al,a2,….an）逆置為（an,al）。

7

3.試編寫(xiě)一個(gè)遍歷及顯示隊(duì)列中元素的算法。

publicvoidnextOrder()

inti,j=front;

for(i=1;i<=size();i++)

j=(j+1)%queueArray.length;

System.out.println(queueArray[j]);

4.設(shè)一循環(huán)隊(duì)列Queue,只有頭指針front,不設(shè)尾指針，另設(shè)一個(gè)內(nèi)含元素

個(gè)數(shù)的計(jì)數(shù)器，試寫(xiě)出相應(yīng)的進(jìn)隊(duì)、出隊(duì)算法。

publicvoidEnQueue（Tobj）

if(count=queueArray.length-l){〃隊(duì)滿(mǎn)

T[]p=(T[])newObject[queueArray.length*2];

inti=front+1,j=l,m=1;

while(m<count){

p[j]=queueArray[i];

i=(i+l)%queueArray.length;

j++;m++；

)

queueArray=p;

front=0;

}

count++；

queueArray[(front+count)%queueArray.length]=obj;

)

publicTDeQueue()

(

if(count==0){

System.out.println("隊(duì)列已空，無(wú)法出隊(duì)！”);

returnnull;

)

front=(front+1)%queueArray.length;

count-;

returnqueueArray[front];

5.設(shè)計(jì)一算法能判斷一個(gè)算術(shù)表達(dá)式中的圓括號(hào)配對(duì)是否正確。（提示：對(duì)

表達(dá)式進(jìn)行掃描，凡遇到“（”就進(jìn)棧，遇到“）”就退出棧頂?shù)摹埃ā?，表達(dá)式

掃描完畢時(shí)棧若為空則圓括號(hào)配對(duì)正確。）

publicstaticbooleanmatching(char[]exp)

intstate=l,i=0;

sequenceStack<Character>s=newsequenceStack<Character>();

/*盅義一個(gè)順序棧*/

while(i<exp.length&&state==l){

switch(exp[i]){

8

case

{

s.push(exp[i]);

i++；

break;

)

case

(

if(!s.isEmpty()){

if(s.getHead()=='('){

s.pop();

i++；

elsestate=O;

)

elsestate=O;

break;

}

default:{i++;break;}

if(s.isEmpty()&&state==1)

returntrue;

elsereturnfalse;

4.7習(xí)題

單項(xiàng)選擇題

1.空串與空格串是相同的，這種說(shuō)法B。

A.正確B.不正確

2.串是一中特殊的線(xiàn)性表，其特殊性體現(xiàn)在一旦_。

A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符

C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符

3.設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作g。

A.連接B.模式匹配C.求子串D.求串長(zhǎng)

4.設(shè)串sl='ABCDEFGLs2=,PQRST,,函數(shù)con(x,y)返回x和y串的連接

串，subs(s,i,j)返回串s的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的子串，len(s)

返回串s的長(zhǎng)度，則con(subs(sl,2,len(s2)),subs(sl,len(s2),2))的結(jié)果串是

D0

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF

5.常對(duì)數(shù)組進(jìn)行的兩種基本操作是C。

A.建立與刪除B.索引和修改C.查找和修改D.查找與索引

9

6.二維數(shù)組M的成員是6個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元，即一個(gè)字節(jié))

組成的串，行下標(biāo)i的范圍從0到8,列下標(biāo)j的范圍從1到10,則存放M

至少需要D個(gè)字節(jié):M的第8列和第5行共占A個(gè)字節(jié)。

①A.90B.180C.240D.540

②A.108B.114C.54D.60

二.填空題(將正確的答案填在相應(yīng)的空中)

1.串的兩種最基本的存儲(chǔ)方式是順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。

2.兩個(gè)串相等的充分必要條件是長(zhǎng)度相等且對(duì)應(yīng)位置字符相等。

3.空串是。個(gè)字符的串，其長(zhǎng)度等于空格串是由一個(gè)或多個(gè)空格字符

組成的串，其長(zhǎng)度等于空格字符個(gè)數(shù)。

4.設(shè)sTHAMoAoTEACHER'淇長(zhǎng)度是14。(□表示空格)

三.算法設(shè)計(jì)題：

1.編寫(xiě)算法，實(shí)現(xiàn)remove(stringt)操作，即從當(dāng)前串中刪除所有和串t相同的

子串。

publicintremove(stringt){

〃在當(dāng)前串中刪除所有與串t相等的子串，并返回刪除的次數(shù)

inttime=0,m;

for(intj=O;j<this.length-t.length+l;j++){

if(this.chars[j]==t.chars[O]){

intx=0;

for(inti=O;i<t.length;i++){

if(this.chars[j+i]==t.chars[i]){

x++;

}

else

break;

)

if(x==t.length){

m=j；

for(inti=j+t.length;i<this.length;i++){

this.chars[m]=this.chars[i];

m++;

}

time++;

this.length-=t.getLength();

returntime;

)

2.編寫(xiě)算法，實(shí)現(xiàn)replace(stringt,stringv)操作，即從當(dāng)前串中用串v替換所

有與串t相等的子串，并返回替換的次數(shù)串的。

publicintreplace(stringt,stringv){

〃在當(dāng)前串中用串v替換所有與串t相等的子串，并返回替換的次數(shù)

intpoor=v.getLength()-t.getLength();

10

intl=O,num=O,m=O,n=O,size=maxSize;

if(maxSize<maxSize+num*poor)

size=maxSize+num*poor;

stringtl=newstring(size);

intcycle=O;

for(inti=O;i<this.length-t.length+1;i++){

if(this.chars[i]==t.chars[0]){

intx=0;

for(intj=0;j<t.length;j++){

if(this.chars[j+i]==t.chars[j])

x++；

else

break;

)

if(x=t.length){

num++;

n=i;

for(l=m;l<n;l++)

tl.chars[tl.length++]=this.chars[l];

for(intj=0;j<v.length;j++)

11.chars[t1.length++]=v.chars[j];

m=i+t.length;

i+=t.length-1;

this.chars=tl.chars;

this.length=tl.length;

returnnum;

}

3.設(shè)A=((a,b),(c,d)),求下列操作結(jié)果:

Tail(Head(A))=?(b)

Tail(Head(Tail(A)))=?(d)

5.7習(xí)題

一.單項(xiàng)選擇題

1.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)

數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（C）個(gè)。

A.4B.5C.6D.7

2.假設(shè)在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為

（B）個(gè)。

A.15B.16C.17D.47

3.假定一棵三叉樹(shù)的結(jié)點(diǎn)數(shù)為50,則它的最小高度為（C）。

A.3B.4C.5D.6

4.在一棵二叉樹(shù)上第4層的結(jié)點(diǎn)數(shù)最多為（D）。

A.2B.4C.6D.8

11

5.用順序存儲(chǔ)的方法將完全二叉樹(shù)中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[l..n],結(jié)點(diǎn)R[i]若

有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（B）。

A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]

6.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為

（D）?

A.24B.48C.72D.53

7.線(xiàn)索二叉樹(shù)是一種（A）結(jié)構(gòu)。

A.邏輯B.邏輯和存儲(chǔ)C.物理D.線(xiàn)性

8.線(xiàn)索二叉樹(shù)中，結(jié)點(diǎn)p沒(méi)有左子樹(shù)的充要條件是（B）。

A.p.lChild=nullB.p.ltag=l

C.p.ltag=l且p.IChild=nullD.以上都不對(duì)

9.設(shè)n,m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（B）。

A.n在m右方B.n在m左方

C.n是m的祖先D.n是m的子孫

10.如果F是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的

（B）?

A.中序B.前序C.后序D.層次序

11.欲實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹(shù)采用

（A）存儲(chǔ)結(jié)構(gòu)。

A.三叉鏈表B.廣義表C.二叉鏈表D.順序

12.下面敘述正確的是（D）。

A.二叉樹(shù)是特殊的樹(shù)B.二叉樹(shù)等價(jià)于度為2的樹(shù)

C.完全二叉樹(shù)必為滿(mǎn)二叉樹(shù)D.二叉樹(shù)的左右子樹(shù)有次序之分

13.任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（A）。

A.不發(fā)生改變B.發(fā)生改變

C.不能確定D.以上都不對(duì)

14.已知一棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)為9個(gè),則最后一層的結(jié)點(diǎn)數(shù)為（B）。

A.1B.2C.3D.4

15.根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹(shù)，該二叉樹(shù)（A）?

A.是完全二叉樹(shù)B.不是完全二叉樹(shù)

C.是滿(mǎn)二叉樹(shù)D.不是滿(mǎn)二叉樹(shù)

二.判斷題

（X）1.二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度不能超過(guò)2,所以二叉樹(shù)是一種特殊的樹(shù)。

（V）2.二叉樹(shù)的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。

（V）3.線(xiàn)索二叉樹(shù)是一種邏輯結(jié)構(gòu)。

（J）4.哈夫曼樹(shù)的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。

（X）5.由二叉樹(shù)的先序序列和后序序列可以唯一確定一顆二叉樹(shù)。

（X）6.樹(shù)的后序遍歷與其對(duì)應(yīng)的二叉樹(shù)的后序遍歷序列相同。）

（X）7.根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹(shù)。

（J）8.滿(mǎn)二叉樹(shù)也是完全二叉樹(shù)。

（X）9.哈夫曼樹(shù)一定是完全二叉樹(shù)。

（X）10.樹(shù)的子樹(shù)是無(wú)序的。

三.填空題

1.假定一棵樹(shù)的廣義表表示為A（B（E）,C（F（H,I,J）,G）,D）,則該樹(shù)的度為

3,樹(shù)的深度為/終端結(jié)點(diǎn)的個(gè)數(shù)為單分支結(jié)點(diǎn)的個(gè)數(shù)為」雙分支結(jié)點(diǎn)的

個(gè)數(shù)為1，三分支結(jié)點(diǎn)的個(gè)數(shù)為2,C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為其孩子結(jié)點(diǎn)為

F和G結(jié)點(diǎn)。

2.設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針

域?yàn)榭盏慕Y(jié)點(diǎn)有n+1個(gè)。

12

3.對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)它為一棵定全二叉樹(shù)時(shí)具有最小高度，即為

llogznl+1,當(dāng)它為一棵單支樹(shù)具有最大高度,即為工。

4.由帶權(quán)為3,9,6,2,5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為國(guó)。

5.在一棵二叉排序樹(shù)上按中序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。

6.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)進(jìn)行鏈接存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)

為2n個(gè),其中n-1個(gè)用于鏈接孩子結(jié)點(diǎn),n+1個(gè)空閑著。

7.在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)個(gè)數(shù)為nO,度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則n0=丁+1。

8.一棵深度為k的滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)總數(shù)為立1，一棵深度為k的完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)

的最小值為絲，最大值為四1。

9.由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有工種不同的形態(tài)。

10.設(shè)高度為h的二叉樹(shù)中只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)

至少為2h-l?

11.一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)，單支樹(shù)形態(tài)達(dá)到最大深度，完全二叉樹(shù)形態(tài)達(dá)到最

小深度。

12.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若一個(gè)結(jié)點(diǎn)的編號(hào)為i（l<iWn）,則它的左孩子結(jié)

點(diǎn)的編號(hào)為2i,右孩子結(jié)點(diǎn)的編號(hào)為2i+l,雙親結(jié)點(diǎn)的編號(hào)為|i/2|。

13.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為理

個(gè)，其中nT個(gè)用于鏈接孩子結(jié)點(diǎn),n+1個(gè)空閑著。

14.哈夫曼樹(shù)是指帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)。

15.