數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）第2版習(xí)題答案-嚴(yán)蔚敏（簡(jiǎn)化版）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）第2版習(xí)題答案—嚴(yán)蔚敏（簡(jiǎn)化版）

第2章線性表

1．選擇題

（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（）。

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

答案：B

解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。

（3）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。

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

答案：B

解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n/2。

（4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。

A．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B．只有一部分，存放結(jié)點(diǎn)值

C．只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針

D．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)

答案：A

（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A．必需是連續(xù)的B．部分地址必需是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以

答案：D

（6）線性表Ｌ在（）狀況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。

A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值Ｂ．需不斷對(duì)Ｌ進(jìn)行刪除插入C．Ｌ中含有大量的結(jié)點(diǎn)Ｄ．Ｌ中結(jié)點(diǎn)結(jié)構(gòu)繁雜

答案：B

解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。

（7）單鏈表的存儲(chǔ)密度（）。

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

答案：C

解釋：存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空

間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度為：D/(D+N)，一定小于1。

（8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A．nB．2n-1C．2nD．n-1

1

答案：A

解釋：當(dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）其次個(gè)表中的元素，只需

要用其次個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。

（9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（）個(gè)元素。

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

答案：B

(10)線性表L=(a1，a2,??an)，以下說(shuō)法正確的是（）。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B．線性表中至少有一個(gè)元素

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

D．除第一個(gè)和最終一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接

后繼。

答案：D

(12)以下說(shuō)法錯(cuò)誤的是（）。構(gòu)時(shí)實(shí)現(xiàn)的效率低

B．順序存儲(chǔ)的線性表可以隨機(jī)存取

C．由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)

A．求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)

答案：D

解釋：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。

(13)在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（）。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)在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。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)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（）。

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;

2

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;答案：C2．算法設(shè)計(jì)題

（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的存儲(chǔ)空間,不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。

[算法描述]

voidMergeList(LinkListpb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)while(papc=pa;pa=pa->next;}//取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移elseif(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}//取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移else//相等時(shí)取La中的元素，刪除Lb中的元素

{pc->next=pa;pc=pa;pa=pa->next;q=pb->next;deletepb;pb=q;

}

}

pc->next=pa?pa:pb;//插入剩余段deleteLb;//釋放Lb的頭結(jié)點(diǎn)}

（6）設(shè)計(jì)一個(gè)算法，通過(guò)一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。[算法描述]

ElemTypeMax(LinkListL){

if(L->next==NULL)returnNULL;

pmax=L->next;//假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值p=L->next->next;

while(p!=NULL){//假使下一個(gè)結(jié)點(diǎn)存在}

returnpmax->data;

if(p->data>pmax->data)pmax=p;//假使p的值大于pmax的值，則重新賦值p=p->next;//遍歷鏈表

第3章棧和隊(duì)列

3

1．選擇題

（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種狀況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1答案：C

解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧

的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的狀況。

（2）若已知一個(gè)棧的入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，若p1=n，則pi為（）。

A．iB．n-iC．n-i+1D．不確定答案：C

解釋：棧是后進(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，?，n，而輸出序列的

第一個(gè)元素為n，說(shuō)明1，2，3，?，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，?，pi=n-i+1。

（3）數(shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。

A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n答案：D

解釋：對(duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，

差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（此題為n），然后與MAXSIZE（此題為n）求余，即（n+r-f)%n。

（4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；答案：A

解釋：x=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點(diǎn)，

即摘除棧頂結(jié)點(diǎn)。

（5）設(shè)有一個(gè)遞歸算法如下intfact(intn){//n大于等于0if(nlink；

解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。

（7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題，尋常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的規(guī)律結(jié)構(gòu)應(yīng)當(dāng)是（）。

A．隊(duì)列B．棧C．線性表D．有序表答案：A

解釋：解決緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線

性表。

（8）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)當(dāng)是（）。

A．2B．3C．4D．6答案：B

解釋：元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，可知元素入隊(duì)的序列是e2、e4、

e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧，易知棧S中最多同時(shí)存在3個(gè)元素，故棧S的容量至少為3。

（9）若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是()。

A．top++;V[top]=x;C．top--;V[top]=x;答案：C

解釋：初始棧頂指針top為n+1，說(shuō)明元素從數(shù)組向量的高端地址進(jìn)棧，又由于元素存儲(chǔ)在向量空間V[1..n]中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。（10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最正確。

A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧答案：D

解釋：利用棧的后進(jìn)先出原則。

（11）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A.僅修改頭指針B.僅修改尾指針

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

解釋：一般狀況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最終一個(gè)元素時(shí)，隊(duì)尾指

針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。

（12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)

5

B．V[top]=x;top++;D．V[top]=x;top--;

=pos;j--){*(p+x)=*p;p--;}//串s的pos后的子串右移，空出串t的位置。

q--;//指針q回退到串t的最終一個(gè)字符

for(j=1;j

解釋：根據(jù)題意可知依照先左孩子、再右孩子、最終雙親結(jié)點(diǎn)的順序遍歷二叉樹(shù)，即后序遍歷二叉樹(shù)。

（8）若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利用（）遍歷方法最適合。

A．前序B．中序C．后序D．按層次答案：C

解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹(shù)的交換，不過(guò)層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大，后序遍歷方法最適合。

（9）在以下存儲(chǔ)形式中，（）不是樹(shù)的存儲(chǔ)形式？

A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法答案：D

解釋：樹(shù)的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹(shù)都能通過(guò)孩子兄弟表示法轉(zhuǎn)換為二叉樹(shù)進(jìn)行存儲(chǔ)。

（10）一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（）。

A．所有的結(jié)點(diǎn)均無(wú)左孩子B．所有的結(jié)點(diǎn)均無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹(shù)答案：C

解釋：由于先序遍歷結(jié)果是“中左右〞，后序遍歷結(jié)果是“左右中〞，當(dāng)沒(méi)有左子樹(shù)時(shí)，就是“中右〞和“右中〞；當(dāng)沒(méi)有右子樹(shù)時(shí)，就是“中左〞和“左中〞。則所有的結(jié)點(diǎn)均無(wú)左孩子或所有的結(jié)點(diǎn)均無(wú)右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無(wú)左孩子與所有的結(jié)點(diǎn)均無(wú)右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，應(yīng)選C。

（11）設(shè)哈夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（）個(gè)葉子結(jié)點(diǎn)。A．99C．101答案：B

解釋：在哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，只有度為0（葉子結(jié)點(diǎn)）和度為2的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹(shù)的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n=n0+n2=2*n0-1，得到n0=100。

（12）若X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）。A．X的雙親B．X的右子樹(shù)中最左的結(jié)點(diǎn)C．X的左子樹(shù)中最右結(jié)點(diǎn)D．X的左子樹(shù)中最右葉結(jié)點(diǎn)答案：C

（13）引入二叉線索樹(shù)的目的是（）。

A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹(shù)中便利的進(jìn)行插入與刪除

C．為了能便利的找到雙親D．使二叉樹(shù)的遍歷結(jié)果唯一答案：A

16

B．100D．102

（14）設(shè)F是一個(gè)森林，B是由F變換得的二叉樹(shù)。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。

A．n?1答案：C

（15）n（n≥2）個(gè)權(quán)值均不一致的字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的表達(dá)中，錯(cuò)誤的是（）。A．該樹(shù)一定是一棵完全二叉樹(shù)B．樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)

C．樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D．樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值答案：A

解釋：哈夫曼樹(shù)的構(gòu)造過(guò)程是每次都選取權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，所以樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。

2．應(yīng)用題

（1）試找出滿足以下條件的二叉樹(shù)

①先序序列與后序序列一致②中序序列與后序序列一致③先序序列與中序序列一致④中序序列與層次遍歷序列一致

答案：先序遍歷二叉樹(shù)的順序是“根—左子樹(shù)—右子樹(shù)〞，中序遍歷“左子樹(shù)—根—右

子樹(shù)〞，后序遍歷順序是：“左子樹(shù)—右子樹(shù)―根＂，根據(jù)以上原則有

①或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù)

②或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù)．③或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)．④或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)

（2）設(shè)一棵二叉樹(shù)的先序序列：ABDFCEGH，中序序列：BFDAGEHC①畫(huà)出這棵二叉樹(shù)。

②畫(huà)出這棵二叉樹(shù)的后序線索樹(shù)。

③將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)（或森林）。AABBCDF

B．nC．n+1D．n+2

CB

A

D

E

C

HEnullFDEFGGHGH③

17

①②

3．算法設(shè)計(jì)題

以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)以下算法：（1）統(tǒng)計(jì)二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)。

[題目分析]假使二叉樹(shù)為空，返回0，假使二叉樹(shù)不為空且左右子樹(shù)為空，返回1，假使二叉樹(shù)不為空，且左右子樹(shù)不同時(shí)為空，返回左子樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹(shù)中葉子節(jié)點(diǎn)個(gè)數(shù)。[算法描述]

intLeafNodeCount(BiTreeT){}

（2）判別兩棵樹(shù)是否相等。

[題目分析]先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等)，假使當(dāng)前節(jié)點(diǎn)不相等，直接返回兩棵樹(shù)不相等;假使當(dāng)前節(jié)點(diǎn)相等，那么就遞歸的判斷他們的左右孩子是否相等。[算法描述]

intcompareTree(TreeNode*tree1,TreeNode*tree2)

//用分治的方法做，比較當(dāng)前根，然后比較左子樹(shù)和右子樹(shù){booltree1IsNull=(tree1==NULL);booltree2IsNull=(tree2==NULL);if(tree1IsNull!=tree2IsNull){return1;}

if(tree1IsNull

}//假使根節(jié)點(diǎn)不相等，直接返回不相等，否則的話，看看他們孩子相等不相等if(tree1->c!=tree2->c){return1;

18

if(T==NULL)

return0;//假使是空樹(shù)，則葉子結(jié)點(diǎn)個(gè)數(shù)為0

return1;//判斷結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)（左孩子右孩子都為空），若是則返回1returnLeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);elseif(T->lchild==NULL}//算法終止

（3）交換二叉樹(shù)每個(gè)結(jié)點(diǎn)的左孩子和右孩子。

[題目分析]假使某結(jié)點(diǎn)左右子樹(shù)為空，返回，否則交換該結(jié)點(diǎn)左右孩子，然后遞歸交換左右子樹(shù)。

[算法描述]

voidChangeLR(BiTree//空二叉樹(shù)寬度為0else

{BiTreeQ[];//Q是隊(duì)列，元素為二叉樹(shù)結(jié)點(diǎn)指針，容量足夠大front=1;rear=1;last=1;

//front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置temp=0;maxw=0;//temp記局部寬度,maxw記最大寬度Q[rear]=bt;//根結(jié)點(diǎn)入隊(duì)列while(frontlchild==NULLT->lchild=T->rchild;T->rchild=temp;return;

}//交換左右孩子

ChangeLR(T->lchild);//遞歸交換左子樹(shù)ChangeLR(T->rchild);//遞歸交換右子樹(shù)

{p=Q[front++];temp++;//同層元素?cái)?shù)加1

if(p->lchild!=null)Q[++rear]=p->lchild;//左子女入隊(duì)if(p->rchild!=null)Q[++rear]=p->rchild;//右子女入隊(duì)if(front>last)//一層終止，

{last=rear;

if(temp>maxw)maxw=temp;

//last指向下層最右元素,更新當(dāng)前最大寬度

temp=0;

}//if}//while

return(maxw);}//終止width

若某個(gè)結(jié)點(diǎn)左子樹(shù)空右子樹(shù)非空或者右子樹(shù)空左子樹(shù)非空，則該結(jié)點(diǎn)為度為1的結(jié)點(diǎn)

第7章查找

20

（14）數(shù)據(jù)表中有10000個(gè)元素，假使僅要求求出其中最大的10個(gè)元素，則采用()算法最節(jié)省時(shí)間。

A．冒泡排序B．快速排序C．簡(jiǎn)單項(xiàng)選擇擇排序D．堆排序答案：D

（15）以下排序算法中，（）不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。

A．希爾排序B．快速排序C．冒泡排序D．堆排序答案：A

解釋：快速排序的每趟排序能將作為樞軸的元素放到最終位置；冒泡排序的每趟排序

能將最大或最小的元素放到最終位置；堆排序的每趟排序能將最大或最小的元素放到最終位置。

2．應(yīng)用題

（1）設(shè)待排序的關(guān)鍵字序列為{12，2，16，30，28，10，16*，20，6，18}，試分別寫(xiě)出訪用以下排序方法，每趟排序終止后關(guān)鍵字序列的狀態(tài)。

①直接插入排序④冒泡排序⑤快速排序⑥簡(jiǎn)單項(xiàng)選擇擇排序⑦堆排序①直接插入排序

[212]1630281016*20618[21216]30281016*20618[2121630]281016*20618[212162830]1016*20618[21012162830]16*20618[210121616*2830]20618[210121616*202830]618[2610121616*202830]18[2610121616*18202830]

④冒泡排序

21216281016*20618[30]212161016*20618[2830]212101616*618[202830]2101216616*[18202830]21012616[16*18202830]210612[1616*18202830]2610[121616*18202830]

26