數據結構（C語言版 第2版）課後習題答案 嚴蔚敏 等 編著

轉自–數據結構（C語言版 第2版）課後習題答案 嚴蔚敏 等 編著
以上沒有第八章答案

數據結構（C語言版 第2版）課後習題答案 嚴蔚敏 編著–含第八章答案

第1章 緒論

5．選擇題

（1）在數據結構中，從邏輯上可以把數據結構分成（ C ）。

A．動態結構和靜態結構 B．緊湊結構和非緊湊結構

C．線性結構和非線性結構 D．內部結構和外部結構

（2）與數據元素本身的形式、內容、相對位置、個數無關的是數據的（ C ）。

A．儲存結構 B．儲存實現

C．邏輯結構 D．運算實現

（3）通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味着（ B ）。

A．數據具有同一特點

B．不僅數據元素所包含的數據項的個數要相同，而且對應數據項的型別要一致

C．每個數據元素都一樣

D．數據元素所包含的數據項的個數要相等

（4）以下說法正確的是（ D ）。

A．數據元素是數據的最小單位

B．數據項是數據的基本單位

C．數據結構是帶有結構的各數據項的集合

D．一些表面上很不相同的數據可以有相同的邏輯結構

解釋：數據元素是數據的基本單位，數據項是數據的最小單位，數據結構是帶有結構的各數據元素的集合。

（5）演算法的時間複雜度取決於（ D ）。

A．問題的規模 B．待處理數據的初態

C．計算機的設定 D．A和B

解釋：演算法的時間複雜度不僅與問題的規模有關，還與問題的其他因素有關。如某些排序的演算法，其執行時間與待排序記錄的初始狀態有關。爲此，有時會對演算法有最好、最壞以及平均時間複雜度的評價。

（6）以下數據結構中，（ A ）是非線性數據結構

A．樹 B．字串 C．佇列 D．棧

6．試分析下面 下麪各程式段的時間複雜度。

（1）

x=90; y=100; 

while(y>0)

if(x>100)

 {x=x-10;y--;}

else x++;

答案：O(1)

解釋：程式的執行次數爲常數階。

（2）

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

for (j=0; j<m; j++)

a[i][j]=0;

答案：O(m*n)

解釋：語句a[i][j]=0;的執行次數爲m*n。

（3）

s=0;
for i=0; i<n; i++)

	for(j=0; j<n; j++)

         s+=B[i][j];

sum=s;

答案：O(n2)

解釋：語句s+=B[i][j];的執行次數爲n2。

（4）

i=1;

     while(i<=n)

        i=i*3;

答案：O(log3n)

解釋：語句i=i*3;的執行次數爲 ëlog3nû。

（5）

x=0;

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

   for (j=1; j<=n-i; j++)

x++;

答案：O(n2)

解釋：語句x++;的執行次數爲n-1+n-2+……＋1= n(n-1)/2。

第2章 線性表

1．選擇題

（1）順序表中第一個元素的儲存地址是100，每個元素的長度爲2，則第5個元素的地址是（ B ）。

A．110 B．108 C．100 D．120

解釋：因爲順序表是連續儲存的，所以第5個元素的地址爲：100+2*( 5 - 1)=108。

（2）在n個結點的順序表中，演算法的時間複雜度是O(1)的操作是（ A ）。

A．存取第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n）

B．在第i個結點後插入一個新結點（1≤i≤n）

C．刪除第i個結點（1≤i≤n）

D．將n個結點從小到大排序

解釋：在順序表中插入、刪除一個結點，平均約移動表中一半元素，時間複雜度爲O(n)；順序表是一種隨機存取結構，按位元置存取元素可通過陣列下標直接定位，時間複雜度是O(1)；（排序的時間複雜度爲O(n2)或O(nlog2n)？）。

（3） 向一個有127個元素的順序表中插入一個新元素並保持原來順序不變，平均要移動 的元素個數爲（ B ）。

A．8 B．63.5 C．63 D．7

解釋：平均移動元素個數爲n/2

（4）鏈接儲存的儲存結構所佔儲存空間（ A ）。

A．分兩部分，一部分存放結點值，另一部分存放表示結點間關係的指針

B．只有一部分，存放結點值

C．只有一部分，儲存表示結點間關係的指針

D．分兩部分，一部分存放結點值，另一部分存放結點所佔單元數

（5）線性表若採用鏈式儲存結構時，要求記憶體中可用儲存單元的地址（ D ）。

A．必須是連續的 B．部分地址必須是連續的

C．一定是不連續的 D．連續或不連續都可以

（6）線性表Ｌ在（ B ）情況下適用於使用鏈式結構實現。

A．需經常修改Ｌ中的結點值 Ｂ．需不斷對Ｌ進行刪除插入

C．Ｌ中含有大量的結點 Ｄ．Ｌ中結點結構複雜

解釋：鏈表插入/刪除數據只需修改指針不需要移動表中數據，鏈表適用長度變化大、頻繁進行插入/刪除操作。

（7）單鏈表的儲存密度（ C ）。

A．大於1 B．等於1 C．小於1 D．不能確定

解釋：儲存密度是指一個結點數據本身所佔的儲存空間和整個結點所佔的儲存空間之比，假設單鏈表一個結點本身所佔的空間爲D，指針域所佔的空間爲N，則儲存密度爲D/(D+N)，即一定小於1。

（8）將兩個各有n個元素的有序表歸併成一個有序表，其最少的比較次數是（ ）。

A．n B．2n-1 C．2n D．n-1

答案：A

解釋：當第一個有序表中所有的元素都小於（或大於）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次，最多比較2n-1次。

（9）在一個長度爲n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時须向後移動（ B ）個元素。

A．n-i B．n-i+1 C．n-i-1 D．I

(10) 線性表L=(a1，a2,……an)，下列說法正確的是（D ）。

A．每個元素都有一個直接前驅和一個直接後繼

B．線性表中至少有一個元素

C．表中諸元素的排列必須是由小到大或由大到小

D．除第一個和最後一個元素外，其餘每個元素都有一個且僅有一個直接前驅和直接後繼。

(11) 建立一個包括n個結點的有序單鏈表的時間複雜度是（ ）。

A．O(1) B．O(n) C．O(n2) D．O(nlog2n)

答案：C

解釋：建立單鏈表的時間複雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結點時需要和已有的結點進行比較 以確定合適的插入位置，所以時間複雜度是O(n2)。

(12) 以下說法錯誤的是（ ）。

A．求表長、定位這兩種運算在採用順序儲存結構時實現的效率不比採用鏈式儲存結構時實現的效率低

B．順序儲存的線性表可以隨機存取

C．由於順序儲存要求連續的儲存區域，所以在儲存管理上不夠靈活

D．線性表的鏈式儲存結構優於順序儲存結構

答案：D

解釋：鏈式儲存結構和順序儲存結構各有優缺點，有不同的適用場合。

(13) 在單鏈表中，要將s所指結點插入到p所指結點之後，其語句應爲（ ）。

A．s->next=p+1; p->next=s;

B．(*p).next=s; (*s).next=(*p).next;

C．s->next=p->next; p->next=s->next;

D．s->next=p->next; p->next=s;

答案：D

(14) 在雙向鏈表儲存結構中，刪除p所指的結點時须修改指針（ ）。

A．p->next->prior=p->prior; p->prior->next=p->next;

B．p->next=p->next->next; p->next->prior=p;

C．p->prior->next=p; p->prior=p->prior->prior;

D．p->prior=p->next->next; p->next=p->prior->prior;

答案：A

(15) 在雙向回圈鏈表中，在p指針所指的結點後插入q所指向的新結點，其修改指針的操作是（ ）。

A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

答案：C

2．演算法設計題

（1）將兩個遞增的有序鏈表合併爲一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的儲存空間, 不另外佔用其它的儲存空間。表中不允許有重複的數據。

[題目分析]

（合併後的新表用一個新的Lc指針。新建一個Lc頭指針，pa和pb分別是鏈表La和Lb的工作指針且初始化爲相應鏈表的第一個結點。從第一個結點開始進行比較，當兩個鏈表La和Lb均未到達表尾結點時，則依次摘取較小元素重新鏈接在Lc表的後面。其中，如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素（注意釋放刪除的元素的空間），這樣確保合併後表中無重複的元素。當一個表到達表尾結點，爲空時，將非空表的剩餘元素直接鏈接在Lc表的最後面。

[演算法描述]

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{//合併鏈表La和Lb，合併後的新表使用頭指針Lc指向
  pa=La->next;  pb=Lb->next;
   //pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點
   Lc=pc=La;  //用La的頭結點作爲Lc的頭結點
   while(pa && pb)
{
if(pa->data<pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
     //取較小者La中的元素，將pa鏈接在pc的後面，pa指針後移
    	else if(pa->data>pb->data){
pc->next=pb;
pc=pb;
pb=pb->next;
}
      //取較小者Lb中的元素，將pb鏈接在pc的後面，pb指針後移
else //相等時取La中的元素，刪除Lb中的元素
{
pc->next=pa;
pc=pa;
pa=pa->next;
q=pb->next;delete pb ;pb =q;（刪除記得要釋放空間）
//q=pb;pb=q->next;delete q;
}
     }
 pc->next=pa?pa:pb;    //插入剩餘段
     delete Lb;          //釋放Lb的頭結點(La的頭結點已賦給了Lc,不需釋放)
}

（2）將兩個非遞減的有序鏈表合併爲一個非遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的儲存空間, 不另外佔用其它的儲存空間。表中允許有重複的數據。
[題目分析]

合併後的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均爲到達表尾結點時，依次摘取其中較小者重新鏈接在Lc表的表頭結點之後，如果兩個表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當一個表到達表尾結點，爲空時，將非空表的剩餘元素依次摘取，鏈接在Lc表的表頭結點之後（前插法）。

[演算法描述]

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )
{//合併鏈表La和Lb，合併後的新表使用頭指針Lc指向
  pa=La->next;  pb=Lb->next;
//pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點
  Lc=pc=La; //用La的頭結點作爲Lc的頭結點
  Lc->next=NULL;
  while(pa||pb)
{//只要存在一個非空表，用q指向待摘取的元素
    if(!pa)  {q=pb;  pb=pb->next;}
//La表爲空，用q指向pb，pb指針後移
    else if(!pb)  {q=pa;  pa=pa->next;}
//Lb表爲空，用q指向pa，pa指針後移
    else if(pa->data<=pb->data)  {q=pa;  pa=pa->next;}
//取較小者（包括相等）La中的元素，用q指向pa，pa指針後移
    else {q=pb;  pb=pb->next;}
//取較小者Lb中的元素，用q指向pb，pb指針後移
     q->next = Lc->next;  Lc->next = q;   
//將q指向的結點插在Lc 表的表頭結點之後
    }
    delete Lb;             //釋放Lb的頭結點
} 

（3）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設計演算法求出A與B的交集，並存放於A鏈表中。

[題目分析]

只有同時出現在兩集閤中的元素纔出現在結果表中,合併後的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均爲到達表尾結點時，如果兩個表中相等的元素時，摘取La表中的元素，刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針後移。當鏈表La和Lb有一個到達表尾結點，爲空時，依次刪除另一個非空表中的所有元素。

[演算法描述]

void Mix(LinkList& La, LinkList& Lb, LinkList& Lc)
{  pa=La->next;pb=Lb->next; 
pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點
Lc=pc=La; //用La的頭結點作爲Lc的頭結點
while(pa&&pb)
{ if(pa->data==pb->data)∥交集併入結果表中。
   { pc->next=pa;pc=pa;pa=pa->next;
     u=pb;pb=pb->next; delete u;}
  else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;}
else {u=pb; pb=pb->next; delete u;}
}
while(pa) {u=pa; pa=pa->next; delete u;}∥ 釋放結點空間
while(pb) {u=pb; pb=pb->next; delete u;}∥釋放結點空間
pc->next=null;∥置鏈表尾標記。
delete Lb;   //釋放Lb的頭結點
   }

（4）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設計演算法求出兩個集合A和B 的差集（即僅由在A中出現而不在B中出現的元素所構成的集合），並以同樣的形式儲存，同時返回該集合的元素個數。

[題目分析]

求兩個集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應結點,所以要儲存待刪除結點的前驅，使用指針pre指向前驅結點。pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均爲到達表尾結點時，如果La表中的元素小於Lb表中的元素，pre置爲La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針後移。當鏈表La和Lb有一個爲空時，依次刪除另一個非空表中的所有元素。

[演算法描述]

void Difference（LinkList& La, LinkList& Lb,int *n）
{∥差集的結果儲存於單鏈表La中，*n是結果集閤中元素個數，呼叫時爲0
pa=La->next; pb=Lb->next;      
∥pa和pb分別是鏈表La和Lb的工作指針,初始化爲相應鏈表的第一個結點
  pre=La;          ∥pre爲La中pa所指結點的前驅結點的指針
  while（pa&&pb）
{if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;}
∥ A鏈表中當前結點指針後移
else if（pa->data>q->data）q=q->next;     ∥B鏈表中當前結點指針後移
    else {pre->next=pa->next;      ∥處理A，B中元素值相同的結點，應刪除
          u=pa; pa=pa->next; delete u;}   ∥刪除結點
}
}

（5）設計演算法將一個帶頭結點的單鏈表A分解爲兩個具有相同結構的鏈表B、C，其中B表的結點爲A表中值小於零的結點，而C表的結點爲A表中值大於零的結點（鏈表A中的元素爲非零整數，要求B、C表利用A表的結點）。

[題目分析]

B表的頭結點使用原來A表的頭結點，爲C表新申請一個頭結點。從A表的第一個結點開始，依次取其每個結點p，判斷結點p的值是否小於0，利用前插法，將小於0的結點插入B表,大於等於0的結點插入C表。

[演算法描述]

void DisCompose(LinkedList A)
{  B=A;
B->next= NULL;    ∥B表初始化
     C=new LNode;∥爲C申請結點空間
     C->next=NULL;     ∥C初始化爲空表
     p=A->next;        ∥p爲工作指針
     while(p!= NULL)
     { r=p->next;      ∥暫存p的後繼
       if(p->data<0)
        {p->next=B->next; B->next=p; }∥將小於0的結點鏈入B表,前插法
       else {p->next=C->next; C->next=p; }∥將大於等於0的結點鏈入C表,前插法
       p=r;∥p指向新的待處理結點。
     }
} 

第3章 棧和佇列

1．選擇題

（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現在（ ）種情況。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1

答案：C

解釋：棧是後進先出的線性表，不難發現C選項中元素1比元素2先出棧，違背了棧的後進先出原則，所以不可能出現C選項所示的情況。

（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列爲p1，p2，p3，…，pn，若p1=n，則pi爲（ ）。

A．i B．n-i C．n-i+1 D．不確定

答案：C

解釋：棧是後進先出的線性表，一個棧的入棧序列是1，2，3，…，n，而輸出序列的第一個元素爲n，說明1，2，3，…，n一次性全部進棧，再進行輸出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）陣列Ｑ［ｎ］用來表示一個回圈佇列，ｆ爲當前佇列頭元素的前一位置，ｒ爲隊尾元素的位置，假定佇列中元素的個數小於ｎ，計算佇列中元素個數的公式爲（ ）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n

答案：D

解釋：對於非回圈佇列，尾指針和頭指針的差值便是佇列的長度，而對於回圈佇列，差值可能爲負數，所以需要將差值加上MAXSIZE（本題爲n），然後與MAXSIZE（本題爲n）求餘，即（n+r-f)%n。

（4）鏈式棧結點爲：(data,link)，top指向棧頂.若想摘除棧頂結點，並將刪除結點的值儲存到x中,則應執行操作（ ）。

A．x=top->data;top=top->link； B．top=top->link;x=top->link；

C．x=top;top=top->link； D．x=top->link；

答案：A

解釋：x=top->data將結點的值儲存到x中，top=top->link棧頂指針指向棧頂下一結點，即摘除棧頂結點。

（5）設有一個遞回演算法如下

    int fact(int n) {  //n大於等於0

         if(n<=0) return 1;

         else return n*fact(n-1);        }

則計算fact(n)需要呼叫該函數的次數爲（ ）。

A． n+1 B． n-1 C． n D． n+2

答案：A

解釋：特殊值法。設n=0，易知僅呼叫一次fact(n)函數，故選A。

（6）棧在 （ ）中有所應用。

A．遞回呼叫 B．函數呼叫 C．表達式求值 D．前三個選項都有

答案：D

解釋：遞回呼叫、函數呼叫、表達式求值均用到了棧的後進先出性質。

（7）爲解決計算機主機與印表機間速度不匹配問題，通常設一個列印數據緩衝區。主機將要輸出的數據依次寫入該緩衝區，而印表機則依次從該緩衝區中取出數據。該緩衝區的邏輯結構應該是（ ）。

A．佇列 B．棧 C． 線性表 D．有序表

答案：A

解釋：解決緩衝區問題應利用一種先進先出的線性表，而佇列正是一種先進先出的線性表。

（8）設棧S和佇列Q的初始狀態爲空，元素e1、e2、e3、e4、e5和e6依次進入棧S，一個元素出棧後即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應該是（　）。

A．2 B．3 C．4 D． 6

答案：B

解釋：元素出隊的序列是e2、e4、e3、e6、e5和e1，可知元素入隊的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少爲3。

（9）若一個棧以向量V[1…n]儲存，初始棧頂指針top設爲n+1，則元素x進棧的正確操作是( )。

A．top++; V[top]=x; B．V[top]=x; top++;

C．top–; V[top]=x; D．V[top]=x; top–;

答案：C

解釋：初始棧頂指針top爲n+1，說明元素從陣列向量的高階地址進棧，又因爲元素儲存在向量空間V[1…n]中，所以進棧時top指針先下移變爲n，之後將元素x儲存在V[n]。

（10）設計一個判別表達式中左，右括號是否配對出現的演算法，採用（　）數據結構最佳。

A．線性表的順序儲存結構 B．佇列

C. 線性表的鏈式儲存結構 D. 棧

答案：D

解釋：利用棧的後進先出原則。

（11）用鏈接方式儲存的佇列，在進行刪除運算時（　）。

A. 僅修改頭指針 B. 僅修改尾指針

C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改

答案：D

解釋：一般情況下只修改頭指針，但是，當刪除的是佇列中最後一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。

（12）回圈佇列儲存在陣列A[0…m]中，則入隊時的操作爲（　）。

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

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

答案：D

解釋：陣列A[0…m]中共含有m+1個元素，故在求模運算時應除以m+1。

（13）最大容量爲n的回圈佇列，隊尾指針是rear，隊頭是front，則隊空的條件是（　）。

A. (rear+1)%n == front B. rear==front

C．rear+1 == front D. (rear-l)%n == front

答案：B

解釋：最大容量爲n的回圈佇列，隊滿條件是(rear+1)%n == front，隊空條件是rear==front。

（14）棧和佇列的共同點是（　）。

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

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

答案：C

解釋：棧只允許在棧頂處進行插入和刪除元素，佇列只允許在隊尾插入元素和在隊頭刪除元素。

（15）一個遞回演算法必須包括（　）。

A. 遞回部分 B. 終止條件和遞回部分

C. 迭代部分 D. 終止條件和迭代部分

答案：B

第5章 樹和二元樹

1．選擇題

（1）把一棵樹轉換爲二元樹後，這棵二元樹的形態是（ ）。

A．唯一的 Ｂ．有多種

C．有多種，但根結點都沒有左孩子 Ｄ．有多種，但根結點都沒有右孩子

答案：A

解釋：因爲二元樹有左孩子、右孩子之分，故一棵樹轉換爲二元樹後，這棵二元樹的形態是唯一的。

（2）由3個結點可以構造出多少種不同的二元樹？（ ）

A．2 B．3 C．4 D．5

答案：D

（3）一棵完全二元樹上有1001個結點，其中葉子結點的個數是（ ）。

A．250 B． 500 C．254 D．501

答案：D

解釋：設度爲0結點（葉子結點）個數爲A，度爲1的結點個數爲B，度爲2的結點個數爲C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二元樹的性質可得B=0或1，又因爲C爲整數，所以B=0，C=500，A=501，即有501個葉子結點。

（4）一個具有1025個結點的二元樹的高h爲（ ）。

A．11 B．10 C．11至1025之間 D．10至1024之間

答案：C

解釋：若每層僅有一個結點，則樹高h爲1025；且其最小樹高爲 ëlog21025û + 1=11，即h在11至1025之間。

（5）深度爲h的滿m叉樹的第k層有（ ）個結點。(1=<k=<h)

A．mk-1 B．mk-1 C．mh-1 D．mh-1

答案：A

解釋：深度爲h的滿m叉樹共有mh-1個結點，第k層有mk-1個結點。

（6）利用二叉鏈表儲存樹，則根結點的右指針是（ ）。

A．指向最左孩子 B．指向最右孩子 C．空 D．非空

答案：C

解釋：利用二叉鏈表儲存樹時，右指針指向兄弟結點，因爲根節點沒有兄弟結點，故根節點的右指針指向空。

（7）對二元樹的結點從1開始進行連續編號，要求每個結點的編號大於其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小於其右孩子的編號，可採用（ ）遍歷實現編號。

A．先序 B. 中序 C. 後序 D. 從根開始按層次遍歷

答案：C

解釋：根據題意可知按照先左孩子、再右孩子、最後雙親結點的順序遍歷二元樹，即後序遍歷二元樹。

（8）若二元樹採用二叉鏈表儲存結構，要交換其所有分支結點左、右子樹的位置，利用（ ）遍歷方法最合適。

A．前序 B．中序 C．後序 D．按層次

答案：C

解釋：後續遍歷和層次遍歷均可實現左右子樹的交換，不過層次遍歷的實現消耗比後續大，後序遍歷方法最合適。

（9）在下列儲存形式中，（ ）不是樹的儲存形式？

A．雙親表示法 B．孩子鏈表表示法 C．孩子兄弟表示法 D．順序儲存表示法

答案：D

解釋：樹的儲存結構有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉換爲二元樹進行儲存。

（10）一棵非空的二元樹的先序遍歷序列與後序遍歷序列正好相反，則該二元樹一定滿足（ ）。

A．所有的結點均無左孩子 B．所有的結點均無右孩子

C．只有一個葉子結點 D．是任意一棵二元樹

答案：C

解釋：因爲先序遍歷結果是「中左右」，後序遍歷結果是「左右中」，當沒有左子樹時，就是「中右」和「右中」；當沒有右子樹時，就是「中左」和「左中」。則所有的結點均無左孩子或所有的結點均無右孩子均可，所以A、B不能選，又所有的結點均無左孩子與所有的結點均無右孩子時，均只有一個葉子結點，故選C。

（11）設哈夫曼樹中有199個結點，則該哈夫曼樹中有（ ）個葉子結點。

A．99 B．100

C．101 D．102

答案：B

解釋：在哈夫曼樹中沒有度爲1的結點，只有度爲0（葉子結點）和度爲2的結點。設葉子結點的個數爲n0，度爲2的結點的個數爲n2，由二元樹的性質n0=n2+1，則總結點數n= n0+n2=2*n0-1，得到n0=100。

（12）若X是二叉中序線索樹中一個有左孩子的結點，且X不爲根，則X的前驅爲（ ）。

A．X的雙親 B．X的右子樹中最左的結點

C．X的左子樹中最右結點 D．X的左子樹中最右葉結點

答案：C

（13）引入二叉線索樹的目的是（ ）。

A．加快查詢結點的前驅或後繼的速度 B．爲了能在二元樹中方便的進行插入與刪除

C．爲了能方便的找到雙親 D．使二元樹的遍歷結果唯一

答案：A

（14）設F是一個森林，B是由F變換得的二元樹。若F中有n個非終端結點，則B中右指針域爲空的結點有（ ）個。

A．n−1 B．n C．n + 1 D．n + 2

答案：C

（15）n（n≥2）個權值均不相同的字元構成哈夫曼樹，關於該樹的敘述中，錯誤的是（ ）。

A．該樹一定是一棵完全二元樹

B．樹中一定沒有度爲1的結點

C．樹中兩個權值最小的結點一定是兄弟結點

D．樹中任一非葉結點的權值一定不小於下一層任一結點的權值

答案：A

解釋：哈夫曼樹的構造過程是每次都選取權值最小的樹作爲左右子樹構造一棵新的二元樹，所以樹中一定沒有度爲1的結點、兩個權值最小的結點一定是兄弟結點、任一非葉結點的權值一定不小於下一層任一結點的權值。

2．應用題

（1）試找出滿足下列條件的二元樹

① 先序序列與後序序列相同 ②中序序列與後序序列相同

③ 先序序列與中序序列相同 ④中序序列與層次遍歷序列相同

答案：先序遍歷二元樹的順序是「根—左子樹—右子樹」，中序遍歷「左子樹—根—右子樹」，後序遍歷順序是：「左子樹—右子樹―根＂，根據以上原則有

① 或爲空樹，或爲只有根結點的二元樹

② 或爲空樹，或爲任一結點至多隻有左子樹的二元樹．

③ 或爲空樹，或爲任一結點至多隻有右子樹的二元樹．

④ 或爲空樹，或爲任一結點至多隻有右子樹的二元樹

（2）設一棵二元樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C

①畫出這棵二元樹。

②畫出這棵二元樹的後序線索樹。

③將這棵二元樹轉換成對應的樹（或森林）。

答案：

第六章

1．選擇題

1-4：CBBB

（5）G是一個非連通無向圖，共有28條邊，則該圖至少有（ ）個頂點。

A．7 B．8 C．9 D．10

答案：C

解釋：8個頂點的無向圖最多有8*7/2=28條邊，再新增一個點即構成非連通無向圖，故至少有9個頂點。

6-12:BABAADC

13-15:CDB

2．應用題

（1）

第七章

1.選擇題

(1)C (2)D (3)無 (4)A (5)B (6)C (7)C (8)C (9)C (10)C (11)B (12)C (13)A (14)D (15)A

就做到這了！

第八章

1.選擇題

1-5：CDBDC 6-10:BCDBC

11-15:BCCCA