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

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

1.5習題

填空題

1.數(shù)據(jù)的物理結(jié)構(gòu)包括順序結(jié)構(gòu)的表示和存儲和鏈式結(jié)構(gòu)的表示和存儲。

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

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

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

輸入、有一個或多個輸出。

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

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

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

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

6.一個算法的效率可分為（時間）效率和（空間）效率。

二.單項選擇題

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

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

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

A.存儲B.物理C.邏輯D.物理和存儲

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

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

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

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

A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性

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

5.計算機算法指的是（C）。

A.計算方法B.排序方法

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

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

1

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

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

三.計算題

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

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

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

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

3.試給出下面兩個算法的時間復(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習題

一.填空題

1.線性表的兩種存儲結(jié)構(gòu)分別為（順序存儲）和（鏈式存儲）。

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

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

3.若經(jīng)常需要對線性表進行插入和刪除操作，則最好采用（鏈式）存儲結(jié)

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

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

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

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

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

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

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

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

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

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

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

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

2

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

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

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

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

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

二.單項選擇題

1.線性表是(A)。

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

C.一個無限序列，可以為空D.一個無限序列，不能為空

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

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

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

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

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

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

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

A.在第i個元素前插入一個元素B.刪除第i個元素

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

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

操作為(B)。

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

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

三.綜合題

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

順序存儲：

優(yōu)點：存儲密度大，存儲空間利用率高，可隨機存取。

缺點：插入或刪除元素時不方便。

鏈式存儲：

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

結(jié)點空間可以動態(tài)申請和釋放；

缺點：存儲密度小，存儲空間利用率低，非隨機存取。

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

將x插入到線性表的適當位置上，以保持線性表的有序性。

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.試分別以不同的存儲結(jié)構(gòu)實現(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é)點head的Next域置為NULL變成一個空鏈表，然后用p結(jié)點

采用頭插法插入到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.試編寫在帶頭結(jié)點的單鏈表中刪除一個最小值結(jié)點的算法。

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è)有一個雙鏈表，每個結(jié)點中除有prior、data和next三個域外，還有一個

訪問頻度域freq,在鏈表被起用之前，其值均初始化為零。每當對鏈表進

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

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

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

static<TextendsComparable>booleanLocateNode(dlinklistL,Tx){

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

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

DuNode<T>q;

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

p=p.next;

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

returnfalse;

else{

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

q=p.prior;

//指針q用于查找p的前面結(jié)點中第一個freq域不小于當前p所指

結(jié)點的freq域的結(jié)點

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

q=q.prior;

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

p.prior.next=p.next;

if(p.next!=null){

p.next.prior=p.prior;

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

prior域

p.prior=q;

p.next=q.next;

q.next=p;

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

returntrue;

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

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

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習題

一.單項選擇題

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

A.edcbaB.decbaC.dceabD.abcde

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

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

(B)o

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

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

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

p3,...?pn,若pl=n,則pi為_C_。

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

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

A.順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)B.散列方式和索引方式

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

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

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

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

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

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

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

7.棧的特點是_B—,隊列的特點是_A_o

A.先進先出B.先進后出

8.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是_B_。

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

6

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

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

A.front==rearB.front!=rear

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

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

A.front==rearB.front!=rear

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

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

rear,則當前隊列中的元素個數(shù)是_A_。

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

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

12.棧和隊列的共同點是_C_o

A.都是先進后出B.都是先進先出

C.只允許在端點處插入和刪除元素D.沒有共同點

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

空的頭結(jié)點）

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.從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，

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

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.向棧中壓入元素的操作是（先移動棧頂指針，后存入元素）。

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

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

4.從循環(huán)隊列中刪除一個元素時，其操作是（先移動隊首指針，后取出元

素）。

5.在具有n個單元的循環(huán)隊列中，隊滿時共有（n-1）個元素。

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

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

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

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

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

當位置上，以保持該表的有序性。

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

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

7

3.試編寫一個遍歷及顯示隊列中元素的算法。

publicvoidnextOrder()

inti,j=front;

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

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

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

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

個數(shù)的計數(shù)器，試寫出相應(yīng)的進隊、出隊算法。

publicvoidEnQueue（Tobj）

if(count=queueArray.length-l){〃隊滿

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("隊列已空，無法出隊！”);

returnnull;

)

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

count-;

returnqueueArray[front];

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

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

掃描完畢時棧若為空則圓括號配對正確。）

publicstaticbooleanmatching(char[]exp)

intstate=l,i=0;

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

/*盅義一個順序棧*/

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習題

單項選擇題

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

A.正確B.不正確

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

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

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

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

A.連接B.模式匹配C.求子串D.求串長

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

串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)

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

D0

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF

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

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

9

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

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

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

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

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

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

1.串的兩種最基本的存儲方式是順序存儲和鏈式存儲。

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

3.空串是。個字符的串，其長度等于空格串是由一個或多個空格字符

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

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

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

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

子串。

publicintremove(stringt){

〃在當前串中刪除所有與串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àn)replace(stringt,stringv)操作，即從當前串中用串v替換所

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

publicintreplace(stringt,stringv){

〃在當前串中用串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習題

一.單項選擇題

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

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

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

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

（B）個。

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

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

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

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

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

11

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

有左孩子，其左孩子的編號為結(jié)點（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é)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為

（D）?

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

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

A.邏輯B.邏輯和存儲C.物理D.線性

8.線索二叉樹中，結(jié)點p沒有左子樹的充要條件是（B）。

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

C.p.ltag=l且p.IChild=nullD.以上都不對

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

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

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

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

（B）?

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

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

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

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

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

A.二叉樹是特殊的樹B.二叉樹等價于度為2的樹

C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次序之分

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

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

C.不能確定D.以上都不對

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

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

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

A.是完全二叉樹B.不是完全二叉樹

C.是滿二叉樹D.不是滿二叉樹

二.判斷題

（X）1.二叉樹中每個結(jié)點的度不能超過2,所以二叉樹是一種特殊的樹。

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

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

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

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

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

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

（J）8.滿二叉樹也是完全二叉樹。

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

（X）10.樹的子樹是無序的。

三.填空題

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

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

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

F和G結(jié)點。

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

域為空的結(jié)點有n+1個。

12

3.對于一個有n個結(jié)點的二叉樹，當它為一棵定全二叉樹時具有最小高度，即為

llogznl+1,當它為一棵單支樹具有最大高度,即為工。

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

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

6.對于一棵具有n個結(jié)點的二叉樹，當進行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)

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

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

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

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

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

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

至少為2h-l?

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

小深度。

12.對于一棵具有n個結(jié)點的二叉樹，若一個結(jié)點的編號為i（l<iWn）,則它的左孩子結(jié)

點的編號為2i,右孩子結(jié)點的編號為2i+l,雙親結(jié)點的編號為|i/2|。

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

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

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

15.