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

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

第2章線性表

1．選擇題

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

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

答案：B

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

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

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

答案：B

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

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

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

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

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

答案：A

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

答案：D

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

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

答案：B

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

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

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

答案：C

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

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

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

1

答案：A

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

要用其次個表中的第一個元素依次與第一個表的元素比較，總計比較n次。

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

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

答案：B

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

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

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

后繼。

答案：D

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

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

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

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

答案：D

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

(13)在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應(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)在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（）。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é)點后插入q所指向的新結(jié)點，其修改指針的操作是（）。

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è)計題

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

[算法描述]

voidMergeList(LinkListpb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點Lc=pc=La;//用La的頭結(jié)點作為Lc的頭結(jié)點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//相等時取La中的元素，刪除Lb中的元素

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

}

}

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

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

ElemTypeMax(LinkListL){

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

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

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

returnpmax->data;

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

第3章棧和隊列

3

1．選擇題

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

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

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

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

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

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

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

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

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

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

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

（4）鏈?zhǔn)綏＝Y(jié)點為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到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é)點的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點，

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

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

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

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

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

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

性表。

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

A．2B．3C．4D．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設(shè)為n+1，則元素x進棧的正確操作是()。

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

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

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

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

（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針

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

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

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

（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。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的最終一個字符

for(j=1;j

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

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

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

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

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

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

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

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

A．所有的結(jié)點均無左孩子B．所有的結(jié)點均無右孩子C．只有一個葉子結(jié)點D．是任意一棵二叉樹答案：C

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

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

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

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

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

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

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

16

B．100D．102

（14）設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（）個。

A．n?1答案：C

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

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

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

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

2．應(yīng)用題

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

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

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

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

①或為空樹，或為只有根結(jié)點的二叉樹

②或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹．③或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹．④或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹

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

②畫出這棵二叉樹的后序線索樹。

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

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

CB

A

D

E

C

HEnullFDEFGGHGH③

17

①②

3．算法設(shè)計題

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

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

intLeafNodeCount(BiTreeT){}

（2）判別兩棵樹是否相等。

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

intcompareTree(TreeNode*tree1,TreeNode*tree2)

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

if(tree1IsNull

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

18

if(T==NULL)

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

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

（3）交換二叉樹每個結(jié)點的左孩子和右孩子。

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

[算法描述]

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

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

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

}//交換左右孩子

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

{p=Q[front++];temp++;//同層元素數(shù)加1

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

{last=rear;

if(temp>maxw)maxw=temp;

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

temp=0;

}//if}//while

return(maxw);}//終止width

若某個結(jié)點左子樹空右子樹非空或者右子樹空左子樹非空，則該結(jié)點為度為1的結(jié)點

第7章查找

20

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

A．冒泡排序B．快速排序C．簡單項選擇擇排序D．堆排序答案：D

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

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

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

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

2．應(yīng)用題

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

①直接插入排序④冒泡排序⑤快速排序⑥簡單項選擇擇排序⑦堆排序①直接插入排序

[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