數(shù)據(jù)結構C語言版(第2版)嚴蔚敏人民郵電出版社課后習題答案

數(shù)據(jù)構造（C說話版）（第2版）

課后習題答案

李冬梅

目錄

第1章緒論1

第2章線性表4

第3章棧和隊列12

第4章串.數(shù)組和廣義表25

第5章樹和二叉樹32

第6章圖41

第7章查找52

第8章排序63

第1章緒論

1.簡述下列概念：數(shù)據(jù).數(shù)據(jù)元素.數(shù)據(jù)項.數(shù)據(jù)對象.數(shù)據(jù)構造.邏輯構造.存儲構造.抽

象數(shù)據(jù)類型.

答案：

數(shù)據(jù)：是客不雅事物的符號暗示，指所有能輸入到盤算機中并被盤算機程序處理的符號

的總稱.如數(shù)學盤算頂用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形.

圖像.聲音.動畫等經(jīng)由過程特別編碼界說后的數(shù)據(jù).

數(shù)據(jù)元素：是數(shù)據(jù)的根本單位，在盤算機中平日作為一個整體進行斟酌和處理.在有些情

形下，數(shù)據(jù)元素也稱為元素.結點.記載等.數(shù)據(jù)元素用于完全地描寫一個對象，如一個學生記

載，樹中棋盤的一個格局（狀況）.圖中的一個極點等.

數(shù)據(jù)項：是構成數(shù)據(jù)元素的.有自力寄義的.不成朋分的最小單位.例如，學生根本信息表

中的學號.姓名.性別等都是數(shù)據(jù)項.

數(shù)據(jù)對象：是性質雷同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集.例如：整數(shù)數(shù)據(jù)對象是集

合N二｛0,±1,±2,…｝，字母字符數(shù)據(jù)對象是集合O｛'A','B',Z,

,'b，,…，'z，｝,學生根本信息表也可是一個數(shù)據(jù)對象.

數(shù)據(jù)構造：是互相之間消失一種或多種特定關系的數(shù)據(jù)元素的集合.換句話說，數(shù)據(jù)構造

是帶“構造”的數(shù)據(jù)元素的集合，“構造”就是指數(shù)據(jù)元素之間消失的關系.

邏輯構造：從邏輯關系上描寫數(shù)據(jù)，它與數(shù)據(jù)的存儲無關，是自力于盤算機的.是以，數(shù)據(jù)

的邏輯構造可以看作是從具體問題抽象出來的數(shù)學模子.

存儲構造：數(shù)據(jù)對象在盤算機中的存儲暗示，也稱為物理構造.

抽象數(shù)據(jù)類型：由用戶界說的，喑示運用問題的數(shù)學模子，以及界說在這個模子上的一組

操縱的總稱.具體包含三部分：數(shù)據(jù)對象.數(shù)據(jù)對象上關系的集合和對數(shù)據(jù)對象的根本操縱的

集合.

2.試舉一個數(shù)據(jù)構造的例子，論述其邏輯構造和存儲構造兩方面的寄義和互相關系.

答案：

例若有一張學生根本信息表，包含學生的學號.姓名.性別.籍貫.專業(yè)等.每個學生根本信

息記載對應一個數(shù)據(jù)元素，學生記載按次序號分列，形成了學生根本信息記載的線性序列.對

于全部表來說，只有一個開端結點（它的前面無記載）和一個終端結點（它的后面無記載），其他

的結點則各有一個也只有一個直接前趨和直接后繼.學生記載之間的這種關系就肯定了學生

表的邏輯構造，即線性構造.

這些學生記載在盤算機中的存儲喑示就是存儲構造.假如用持續(xù)的存儲單元（如用數(shù)組暗

示）來存放這些記載，則稱為次序存儲構造；假如存儲單元不持續(xù)，而是隨機存放各個記載，然

后用指針進行鏈接，則稱為鏈式存儲構造.

即雷同的邏輯構造，可以對應不合的存儲構造.

3.簡述邏輯構造的四種根本關系并畫出它們的關系圖.

答案：

(1)集合構造

數(shù)據(jù)元素之間除了“屬于統(tǒng)一集合”的關系外，別無其他關系.例如，肯定一邏輯學生是

否為班級成員，只需將班級看做一個集合構造.

(2)線性構造

數(shù)據(jù)元素之間消失一對一的關系.例如，將學生信息數(shù)據(jù)按照其入學報到的時光先后次序

進行分列，將構成一個線性構造.

(3)樹構造

數(shù)據(jù)元素之間消失一對多的關系.例如，在班級的治理系統(tǒng)中，班長治理多個組長，每位組

長治理多名組員，從而構成樹形構造.

(4)圖構造或網(wǎng)狀構造

數(shù)據(jù)元素之間消失多對多的關系,例如，多位同窗之間的同伙關系，任何兩位同窗都可所

以同伙，從而構成圖形構造或網(wǎng)狀構造.

個中樹構造和圖構造都屬于非線性構造.

°18°

ooQO-

四類根本邏輯構造關系圖

4.存儲構造由哪兩種根本的存儲辦法實現(xiàn)？

答案：

(1)次序存儲構造

次序存儲構造是借助兀素在存儲器中的相對地位來暗不數(shù)據(jù)兀素之間的邏輯關系，平日

借助程序設計說話的數(shù)組類型來描寫.

(2)鏈式存儲構造

次序存儲構造請求所有的元素依次存放在一片持續(xù)的存儲空間中，而鏈式存儲構造，無需

占用一整塊存儲空間.但為了暗示結點之間的關系，須要給每個結點附加指針字段，用于存放

后繼元素的存儲地址.所以鏈式存儲構造平日借助于程序設計說話的指針類型來描寫.

5.選擇題

(1)在數(shù)據(jù)構造中，從邏輯上可以把數(shù)據(jù)構造分成().

A.動態(tài)構造和靜態(tài)構造B.緊湊構造和非緊湊構造

C.線性構造和非線性構造D.內部構造和外部構造

答案：C

答案；O(m*n)

解釋：語句a[i][j]=0;的履行次數(shù)為m*n.

(3)s=0;

fori=0;i<n;i++)

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

s+=B[i][j];

sum=s;

答案；0(n2)

解釋：語句s+=的履行次數(shù)為r?.

(4)i=l;

while(i<=n)

i=i*3;

答案：0(log3〃)

解釋：語句i=i*3;的履行次數(shù)為Llog3〃」.

(5)x=0;

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

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

x++;

答案：O(rf)

解釋：語句x++;的履行次數(shù)為nT+n-2+....+1=n(n-l)/2.

(6)x=n;//n>l

y=o；

while(x>(y+1)*(y+1))

y++;

答案：0(。)

解釋：語句y++;的履行次數(shù)為L〃」.

第2章線性表

1.選擇題

(1)次序表中第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地

址是().

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

答案：B

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

(2)在n個結點的次序表中,算法的時光龐雜度是0(1)的操縱是().

A.拜訪第i個結點（14iWn）和求第i個結點的直接前驅（2WiWn）

B.在第i個結點后拔出一個新結點（iWiWn）

C.刪除第i個結點（IWiWn）

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

答案：A

解釋：在次序表中拔出ordelete一個結點的時光龐雜度都是0（n）,排序的時光龐雜度

為O（M）或O（nlog2〃）.次序表是一種隨機存取構造，拜訪第i個結點和求第i個結點的直接前

驅都可以直接經(jīng)由過程數(shù)組的下標直接定位,時光龐雜度是0（1）.

（3）向一個有127個元素的次序表中拔出一個新元素并保持本來次序不變，平均要移動

的元素個數(shù)為（）.

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

答案：B

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

（4）鏈接存儲的存儲構造所占存儲空間（）.

A.分兩部分，一部分存放結點值，另一部分存放暗示結點間關系的指針

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

C.只有一部分,存儲暗示結點間關系的指針

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

答案：A

（5）線性表若采取鏈式存錯構造時，請求內存中可用存儲單元的地址（）.

A.必須是持續(xù)的B.部分地址必須是持續(xù)的

C.必定是不持續(xù)的D.持續(xù)或不持續(xù)都可以

答案：D

（6）線性表L在（）情形下實用于運用鏈式構造實現(xiàn).

A.需經(jīng)常修正L中的結點值B.需不竭對L進行刪除拔出

C.L中含有大量的結點D.L中結點構造龐雜

答案：B

解釋：鏈表最大的長處在于拔出和刪除時不須要移動數(shù)據(jù),直接修正指針即可.

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

A.大于1B,等于1C.小于1D.不克不及肯定

答案：C

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

間之比，假設單鏈表一個結點本身所占的空間為D,指針域所占的空間為N,則存儲密度

為：D/（D+N）,必定小于1.

（8）將兩個各有n個元素的有序表歸并成一個有序表，其起碼的比較次數(shù)是（）.

A.nB.2n-1C.2nD.n-1

答案：A

解釋：當?shù)谝粋€有序表中所有的元素都小于（或大于）第二個表中的元素,只須要

用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次.

(9)在?個氏度為n的次序表中，在第i個元素(iWiWn+1)之前拔山?個新元素時須

向后移動()個元素.

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

答案：B

(10)線性表L=(a.,a2,……a)下列說法準確的是().

A.每個元素都有一個直接前驅和一個直接后繼

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

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

D.除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后

繼.

答案：D

(11)創(chuàng)建一個包含〃個結點的有序單鏈表的時光龐雜度是().

A.0(1)B.O(n)C.0(n2)D.O(nlog2n)

答案：C

解釋：單鏈表創(chuàng)建的時光龐雜度是O(n),而要樹立一個有序的單鏈表，則每生成一

個新結點時須要和已有的結點進行比較,肯定合適的拔出地位，所以時光龐雜度是O(n2).

(12)以下說法錯誤的是().

A.求表長.定位這兩種運算在采取次序存儲構造時實現(xiàn)的效力不比采取鏈式存儲構造

時實現(xiàn)的效力低

B.次序存儲的線性表可以隨機存取

C.因為次序存儲請求持續(xù)的存儲區(qū)域，所以在存儲治理上不敷靈巧

D.線性表的鏈式存儲構造優(yōu)于次序存儲構造

答案：D

解釋：鏈式存儲構造溫柔序存儲構造各有優(yōu)缺陷，有不合的實用處合.

(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->piior-q;q->piior-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)將兩個遞增的有序鏈表歸并為一個遞增的有序鏈表.請求成果鏈表仍運用本來兩個

鏈表的存儲空間，不別的占用其它的存儲空間.表中不許可有反復的數(shù)據(jù).

［標題剖析］

歸并后的新表運用頭指針Lc指向，pa和pb分離是鏈表La和Lb的工作指針，初始化為

響應鏈表的第一個結點，從第一個結點開端進行比較，當兩個鏈表La和Lb均為到達表尾結點

時，依次摘取個中較小者從新鏈接在Lc表的最后.假如兩個表中的元素相等，只摘取La表中

的元素，刪除Lb表中的元素，如許確保歸并后表中無反復的元素.當一個表到達表尾結點，為

空時，將非空表的殘剩元素直接鏈接在Lc表的最后.

［算法描寫］

voidMergeList(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指針后移

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的頭結點

)

(2)將兩個非遞減的有序鏈表歸并為一個非遞增的有序鏈表.請求成果鏈表仍運用本來

兩個鏈表的存儲空間，不別的占用其它的存儲空間.表中許可有反復的數(shù)據(jù).

［標題剖析］

歸并后的新表運用頭指針Lc指向，pa和pb分離是鏈表La和Lb的工作指針，初始化為

響應鏈表的第一個結點，從第一個結點開端進行比較，當兩個鏈表La和Lb均為到達表尾結點

時，依次摘取個中較小者從新鏈接在Lc表的表頭結點之后，假如兩個表中的元素相等，只摘取

La表中的元素，保存Lb表中的元素.當?個表到達表尾結點，為空時，將非空表的殘剩元素依

次摘取，鏈接在Lc表的表頭結點之后.

［算法描寫］

voidMergeList(LinkList&La,LinkList&La,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指針后移

elseif(!pb){q=pa;pa=pa->next;}

//Lb表為空，用q指向pa,pa指針后移

elseif(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表的表頭結點之后

)

deleteLb;//釋放Lb的頭結點

)

(3)已知兩個鏈表A和B分離暗示兩個集合，其元素遞增分列.請設盤算法求出A與B

的交集，并存放于A鏈表中.

［標題剖析］

只有同時出如今兩集合中的兀素才出如今成果表中，歸并后的新表運用頭指針Lc指

向.pa和pb分離是鏈表La和Lb的工作指針，初始化為響應鏈表的第一個結點，從第一個結

點開端法行比較，當兩個鏈表La和Lb均為到達表尾結點;時，假如兩個表中相等的元素時?，摘

取La表中的元素，刪除Lb表中的元素；假如個中一個表中的元素較小時，刪除此表中較小的

元素，此表的工作指針后移.當鏈表La和Lb有一個到達表尾結點，為空時，依次刪除另一個非

空表中的所有元素.

［算法描寫］

voidMix(LinkList&La,LinkList&Lb,LinkList&Lc)

{pa=La->next;pb=Lb->next;

pa和pb分離是鏈表La和Lb的工作指針，初始化為響應鏈表的第一個結點

Lc二pc=La;//用La的頭結點作為Lc的頭結點

whi1e(pa&&pb)

{if(pa->data==pb->data)〃交集并入成果表中.

{pc->next=pa;pc=pa;pa=pa->next;

u=pb;pb=pb->next;deleteu;}

elseif(pa->data<pb->data)(u=pa;pa=pa->next;deleteu;}

else{u=pb;pb=pb->next;deleteu;}

)

while(pa){u-pa;pa-pa->next;deleteu;}〃釋放結點空間

while(pb){u=pb;pb=pb->next;deleteu;}〃釋放結點空間

pc->next=nul1;//置鏈表尾標識表記標幟.

deleteLb;〃釋放Lb的頭結點

)

(4)已知兩個鏈表A和B分離暗示兩個集合，其元素遞增分列.請設盤算法求出兩個集

合A和B的差集(即僅由在A中消失而不在B中消失的元素所構成的集合)，并以同樣的情

勢存儲，同時返回該集合的元素個數(shù).

［標題剖析1

求兩個集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的響應結

點，所以要保管待刪除結點的前驅，運用指針pre指向前驅結點.pa和pb分離是鏈表La和

Lb的工作指針，初始化為響應鏈表的第一個結點，從第一個結點開端進行比較，當兩個鏈表La

和Lb均為到達表尾結點時，假如La表中的元素小于Lb表中的元素，pre置為La表的工作指

針pa刪除Lb表中的元素；假如個中一個表中的元素較小時，刪除此表中較小的元素，此表的

工作指針后移.當鏈表La和Lb有一個為空時，依次刪除另一個非空表中的所有元素.

［算法描寫］

voidDifference(LinkList&La,LinkList&Lb,int*n)

{〃差集的成果存儲于單鏈表La中，*n是成果集合中元素個數(shù)，挪用時為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鏈表中當前結點指針后移

elseif(pa->data>q->data)q=q->next;〃B鏈表中當前結點指針后移

else{pre->next=pa->next;〃處理A,B中元素值雷同的結點，應刪除

u=pa;pa=pa->next;deleteu;}〃刪除結點

(5)設盤算法將一個帶頭結點的單鏈表A分化為兩個具有雷同構造的鏈表B.C,個中B

表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點(鏈表A中的元

素為非零整數(shù)，請求B.C表運用A表的結點).

［標題剖析］

B表的頭結點運用本來A表的頭結點，為C表新申請一個頭結點.從A表的第一個結點開

端，依次取其每個結點P,斷定結點P的值是否小于0,運用前插法，將小于0的結點拔出B表,

大于等于0的結點拔出C表.

［算法描寫］

voidDisCompose(LinkecListA)

{B=A;

B->next-NULL;〃B表初始化

C=newLNode;〃為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指向新的待處理結點.

}

)

(6)設計一個算法，經(jīng)由過程一趟遍歷在單鏈表中肯定值最大的結點.

［標題剖析］

假定第一個結點中數(shù)據(jù)具有最大值，依次與下一個元素比較，若其小于下一個元素，則設

其下一個元素為最大值，反復進行比較，直到遍歷完該鏈表.

［算法描寫］

ElemTypeMax(LinkListL){

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

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

p=L->next->next;

while(p!=NULL){//假如下一個結點消失

if(p->data>pmax->data)pmax=p;//假如p的值大于pmax的值，則從新

賦值

p=p-〉next;//遍歷鏈表

}

returnpmax->data;

(7)設計一個算法，經(jīng)由過程遍歷一趟，將鏈表中所有結點的鏈接偏向逆轉，仍運用原表

的存儲空間.

［標題剖析］

從首元結點開端,逐個地把鏈表L的當前結點p拔出新的鏈表頭部.

［算法描寫］

voidinverse(LinkList&L)

{//逆置帶頭結點的單鏈表L

p=L->next;L->next=NULL;

while(p){

q=p->next;//q指向*p的后繼

p->next-L->next;

L->next=p;//*p拔出在頭結點之后

P二q；

)

}

(8)設計一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素(mink

和maxk是給定的兩個參數(shù)，其值可以和表中的元素雷同，也可以不合).

［標題剖析］

分離查找第一個值》mink的結點和第一個值2maxk的結點;，再修正指針，刪除值大于

mink且小于maxk的所有元素.

［算法描寫］

voiddelete(LinkList&L,intmink,intmaxk){

p=L->next;//首元結點

while(p&&p->data<=mink)

{pre=p;p=p->next;}//查找第一個值>mink的結點

if(p)

{whi1e(p&&p->data<maxk)p=p->next;

//查找第一個值^niaxk的結點

q=pre->next;pre->next=p;//修正指針

while(q!=p)

{s=q->next;deleteq;q=s;}//釋放結點空間

}//if

}

(9)已知p指向雙向輪回鏈表中的一個結點，其結點構造為data,prior,next三個域，

寫出算法change(p),交流p所指向的結點和它的前綴結點的次序.

［標題剖析］

知道雙向輪回鏈表中的一個結點，與前驅交流涉及到四個結點(P結點，前驅結點，前驅

的前驅結點，后繼結點)六條鏈.

［算法描寫］

voidExchange(LinkedListp)

〃P是雙向輪回鏈表中的一個結點，本算法將P所指結點與其前驅結點交流.

{q=p->l1ink;

q->l1ink>rlink=p;//p的前驅的前驅之后繼為p

p->llink=q->llink;〃p的前驅指向其前驅的前驅.

q->rlink=p->rlink;//p的前驅的后繼為p的后繼.

q->l1ink=p;〃p與其前驅交流

p->rlink->l1ink=q;〃p的后繼的前驅指向原p的前驅

p->rlink=q;〃p的后繼指向其本來的前驅

}〃算法exchange停滯.

(10)己知長度為n的線性表A采取次序存儲構造，請寫一時光龐雜度為O(n).空間龐

雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素.

[標題剖析]

在次序存儲的線性表上刪除元素，平日要涉及到一系列元素的移動(刪第i個元素，第

i+1至第n個元素要依次前移).本題請求刪除線性表中所有值為item的數(shù)據(jù)元素，并未請

求元素間的相對地位不變.是以可以斟酌設頭尾兩個指針(i=l,j=n),從兩頭向中央移動，

凡碰到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素地位.

[算法描寫]

voidDelete(ElemTypeA[],intn)

〃A是有n個元素的一維數(shù)組，本算法刪除A中所有值為item的元素.

{i=l;六n;〃設置數(shù)組低.高端指針(下標).

while(i<j)

{while(i<j&&A[i]!=item)i++;〃若值不為item,左移指針.

if(i<j)while(i<j&&A[j]==item)j一；〃若右端元素為item,指針左移

if(i<j)A[i++]=A[j—];}

第3章棧和隊列

1.選擇題

(1)若讓元素1,2,3,4,5依次進棧，則出棧次序不成能出如今()種情形.

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

答案：C

解釋：棧是落后先出的線性表，不難發(fā)明C選項中元素1比元素2先出棧，違反了棧的

落后先出原則，所以不成能消失C選項所示的情形.

(2)若已知一個棧的入棧序列是1,2,3,…,n,其輸出序列為pl,p2,p3,…,pn,若pl=n,則

pi為().

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

答案：C

解釋：棧是落后先出的線性表,一個棧的入棧序列是1,2,3,…,n,而輸出序列的第一個元

素為n,解釋1,2,3,…,n一次性全體進棧，再進行輸出，所以pl=n,p2=n-l,-,pi=n-i+l.

(3)數(shù)組Q[n]用來喑示?個輪回隊列，f為當前隊列頭元素的前?地位，r為隊尾元

素的地位,假定隊列中元素的個數(shù)小于n,盤算隊列中元素個數(shù)的公式為().

A.r-fB.(n+f-r)%nC.n+r-fD.(n+r-f)%n

答案：D

解釋：對于非輪回隊歹IJ,尾指針和頭指針的差值等于隊列的長度，而對于輪回隊歹U,差值

可能為負數(shù),所以須要將差值加上MAXSIZE(本題為n),然后與MAXSIZE(本題為n)求

余，即(n+r-f)%n.

(4)鏈式棧結點為：(data,link),lop指向棧頂.若想摘除棧頂結點，并將刪除結點的值保

管到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)設有一個遞歸算法如下

intfact(intn){//n大于等于0

if(n<=0)return1;

elsereturnn*fact(n-1);}

則盤算fact(n)須耍挪用該函數(shù)的次數(shù)為().

A.n+1B.n-1C.nD.n+2

答案：A

解釋：特別值法.設n=(),易知僅挪用一次fact(n)函數(shù)，故選A.

(6)棧在()中有所運用.

A.遞歸挪用B.函數(shù)挪用C.表達式求值D.前三個選項都有

答案：D

解釋：遞歸挪用.函數(shù)挪用.表達式求值均用到了棧的落后先出性質.

(7)為解決盤算機主機與打印機間速度不匹配問題，平日設一個打印數(shù)據(jù)緩沖區(qū).主機將

要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中掏出數(shù)據(jù).該緩沖區(qū)的邏輯構

造應當是()?

A.隊列B.棧C.線性表D.有序表

答案：A

解釋：解決緩沖區(qū)問題應運用一種先輩先出的線性表，而隊列恰是一和先輩先出的線

性表.

(8)設棧S和隊列Q的初始狀況為空，元素el.e2.e3.e4.e5和e6依次進入棧S,一個元

素出棧后即進入Q,若6個元素出隊的序列是e2.e4.e3.e6.e5和el,則棧S的容量至少應當是

().

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

答案：B

解釋：兀素山隊的序列是e2.e4.e3.e6.e5和e1,可知元素入隊的序列是e2.e4.e3.e6.e5

和el,即元素出棧的序列也是e2.e4.e3.e6.e5和el,而元素el.e2.e3.e4.e5和e6依次進入棧,

易知棧S中最多同時消失3個元素，故棧S的容量至少為3.

（9）若一個棧以向量存儲,初始棧頂指針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,解釋元素從數(shù)組向量的高端地址進棧,又因為元素存

儲在向量空間中，所以進棧時top指針先下移變成n,之后將元素x存儲在V[n].

（10）設計一個判別表達式中左，右括號是否配對消失的算法，采?。ǎ?shù)據(jù)構造最佳.

A,線性表的次序存儲構造B.隊列

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

答案：D

解釋：運用棧的落后先出原則.

（II）用鏈接方法存儲的隊列，在進行刪除運算時（）.

A,僅修正頭指針B.僅修正尾指針

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

答案：D

解釋：一般情形下只修正頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也

喪掉了，是以需對隊尾指針從新賦值.

（12）輪回隊列存儲在數(shù)組中，則入隊時的操縱為（）.

A.rear=rear+1B.rear=（rear+l）%（m-l）

C.rear=（rear+1）%mD.rear=（rear+1）%（m+1）

答案：D

解釋：數(shù)組A[0.?m]中共含有m+1個元素，故在求模運算時應除以m+l.

（13）最大容量為n的輪回隊列，隊尾指針是rear,隊頭是front,則隊空的前提是

（）.

A.（rear+l）%n==frontB.rear==front

C.rear+1==frontD.（rear-1）%n==front

答案：B

解釋:最大容量為n的輪回隊列，隊滿前提是（rear+l）%n=二front,隊空前提是

rear二二front.

（14）棧和隊列的配合點是（）.

A,都是先輩先出B.都是先輩后出

C,只許可在端點處拔出和刪除元素D.沒有配合點

答案：C

解釋：棧只許可在棧頂處進行拔出和刪除元素，隊列只許可在隊尾拔出元素和在隊頭

刪除元素.

(15)?個遞歸算法必須包含().

A.遞歸部分B.終止前提和遞歸部分

C,迭代部分D.終止前提和迭代部分

答案：B

2.算法設計題

(1)將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中,棧底分離處干數(shù)組的兩頭.

當笫0號棧的棧頂指車Iiop[0]等于-1時該棧為空，當笫1號棧的棧頂指針iop[l]等于m時該

棧為空.兩個棧均從兩頭向中央增長.試編寫雙棧初始化、斷定?？?棧滿.進棧和出棧等算法的

函數(shù).雙棧數(shù)據(jù)構造的界說如下：

Typedefstruct

{inttop[2],bot[2];〃棧頂和棧底指針

SElemType*V;〃棧數(shù)組

intm;〃棧最大可容納元素個數(shù)

JDblStack

[標題剖析]

兩棧共享向量空間，將兩棧棧底設在向量兩頭，初始時，左棧頂指針為-1,右棧頂為m.兩

棧頂指針相鄰時為棧滿.兩棧頂相向.迎面增長，棧頂指針指向棧頂元素.

[算法描寫]

(1)棧初始化

intInit()

{S.top[0]=-1;

S.top[1]=m;

return1;〃初始化成功

)

(2)入棧操縱：

intpush(stkS,inti,intx)

〃i為棧號,i=0暗示左棧,i=l為右棧,x是入棧元素.入棧成功返回1,掉敗返回0

{){cout<<“棧號輸入不合錯誤”<vendl;exit(O);)

if(S.top[1]-S.top[0]==1){coul<v"棧已滿"<<endl;return(O);}

switch(i)

{case0:S.V[++S.top[0]]=x;return(1);break;

case1:S.V[--S.top[l]]=x;return(1);

}

}//push

(3)退棧操縱

ElemTypepop(stkS,inti)

〃退棧.i代表棧號,i=0時為左棧,i=l時為右棧.退棧成功時返回退棧元素

〃不然返回

{if(i<0||i>l){cout<<“棧號輸入錯誤”<<endl;exit(O);}

switch(i)

{case0:if(S.top[0]==?l){cout<v"?？铡?lt;<endl;return(-1);}

elsereturn(S.V[S.top[0]--]);

case1:if(S.top[1]==m{cout<<"?？?<vendl;return(-1);)

elsereturn(S.V[S.top[1]++])；

}!/switch

}〃算法停滯

(4)斷定?？?/p>

intEmptyO;

{return(S.top[0]==-1&&S.topf1l==m);

)

[算法評論辯論]

請留意算法中兩棧入棧和退棧時的棧頂指針的盤算.左棧是平日意義下的棧，而右棧入棧

操縱時，其棧頂指針左移(減1)，退棧時，棧頂指針右移(加1).

(2)回文是斧正讀反讀均雷同的字符序列，如“abba”和“abdba”均是回文，但

“good”不是回文.試寫一個算法剖斷給定的字符向量是否為回文.(提醒：將一半字符入棧)

[標題剖析]

將字符串前一半入棧，然后，棧中元素和字符串后一半進行比較.即將第一個出棧元素和

后一半串中第一個字符比較，若相等，則再出棧一個元素與后一個字符比較，……，直至?？?，

結論為字符序列是回文.在出棧元素與串中字符比較不等時，結論字符序列不是回文.

[算法描寫]

#defineStackSize100//假定預分派的棧空間最多為100個元素

typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符

typedefstruct

{DataTypedata[StackSize];

inttop;

}SeqStack;

intTslluiwen(char*t)

{//斷定t字符向量是否為回文，若是，返回1,不然返回0

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

len=strlen(t);//求向量長度

for(i=0;i<len/2;i++)//將一半字符入棧

Push(&s,t[i]);

whi1c(!EmptyStack(&s))

{//每彈出一個字符與響應字符比較

temp=Pop(&s);

if(temp!=S[i])return0;//不等則返回0

elsei++;

)

return1;//比較完畢均相等則返回1

)

(3)設從鍵盤輸入一整數(shù)的序列：ai,a2,a3,...,an,試編寫算法實現(xiàn)：用棧構造存儲輸入

的整數(shù)，當aiW-1時，將ai進棧;當ai=-l時,輸出棧頂整數(shù)并出棧.算法應對平營情形(入棧滿

等)給出響應的信息.

[算法描寫]

#def1nemaxsize?？臻g容量

voidInOutS(ints[maxsize])

//s是元素為整數(shù)的棧，本算法進行入棧和退棧操縱.

{inttop=0;//top為棧頂指針，界說top=0時為?？?

for(i=l;i<=n;i++)//n個整數(shù)序列作處理.

{cin?x);〃從鍵盤讀入整數(shù)序列.

if(x!=-l)//讀入的整數(shù)不等于T時入棧.

{if(top==maxsize-l){cout<<"棧滿"<<endl;exit(0);}

elses[++top]=x;〃x入棧.

)

else〃讀入的整數(shù)等于-1時退棧.

{if(top==0){cout<<“?？铡?lt;<endl;exit(0);}

elsecout<<“出棧元素是"<<s[top-]<<endl;}

)

}〃算法停滯.

(4)從鍵盤上輸入一個后綴表達式，試編寫算法盤算表達式的值.劃定：逆波蘭表達式

的長度不超出一行，以$符作為輸入停滯，操縱數(shù)之間用空格分隔，操縱符只可能有+.-.*./四

種運算.例如:23434+2*$.

[標題剖析]

逆波蘭表達式(即后綴表達式)求值規(guī)矩如下：設立運算數(shù)棧OPND,對表達式從左到右掃

描(讀入)，當表達式中掃描到數(shù)時，壓入0PND棧.當掃描到運算符時，從0PND退出兩個數(shù)，進

行響應運算，成果再壓入0PND棧.這個進程一向進行到讀出表達式停滯符$，這時0PND棧中

只有一個數(shù)，就是成果.

[算法描寫]

floatexpr()

〃從鍵盤輸入逆波蘭表達式，以'$'暗示輸入停滯，本算法求逆波蘭式表達式的值.

{float0PND[30];//OPND是操縱數(shù)棧.

init(OPND);//兩棧初始化.

floatnum=0.0;//數(shù)字初始化.

cin>>x;//x是字符型變量.

while(x!='$')

{switch

{case'O'<=x<=,9':

while((x>=JO'&&x<=’9')||x二二'「)〃拼數(shù)

if(x!='.')//處理整數(shù)

{num=num*10+(ord(x)-ord('O'));cin>>x;}

else//處理小數(shù)部分.

{scale=10.0;cin>>x;

while(x>=,O'&&x<二'9')

{num=nun+(ord(x)-ord(，0')/sca1e;

scale=scale*10;cin>>x;}

}//else

push(OPND,num);num=0.0;//數(shù)壓入棧，下個數(shù)初始化

casex='':break;//遇空格，持續(xù)讀下一個字符.

casex=，+':push(OPND,pop(OPND)+pop(OPND));break;

casex='-':xl=pop(OPND);x2=pop(OPND);push(OPND,x2-xl);break;

casex=，*':push(OPND,pop(OPND)*pop(OPND));break;

casex=:xl=pop(OPND);x2=pop(OPND);push(OPND,x2/xl);break;

default://其它符號不作處理.

}//停滯switch

cin>>x;//讀入表達式中下一個字符.

}〃停滯whi1e(x!='$')

cout<<“后綴表達式的值為"<<pop(OPND);

}〃算法停滯.

[算法評論辯論]假設輸入的后綴表達式是準確的，未作錯誤檢討.算法中拼數(shù)部分是焦點.

若碰到大于等于’0’且小于等于‘9’的字符，以為是數(shù).這種字符的序號減去字符'0'的

序號得出數(shù).對于整數(shù)，每讀入一個數(shù)字字符，前面得到的部分數(shù)要乘上10再加新讀入的數(shù)得

到新的部分數(shù).當讀到小數(shù)點，以為數(shù)的整數(shù)部分已完，耍接著處理小數(shù)部分.小數(shù)部分的數(shù)要

除以10(或10的幕數(shù))變成十分位，百分位，千分位數(shù)等等，與前面部分數(shù)相加.在拼數(shù)進程

中，若遇非數(shù)字字符，暗示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復為0,預備下一個數(shù).

這時對新讀入的字符進入.7'及空格的斷定，是以在停滯處理數(shù)字字符

的case后，不克不及參加break語句.

(5)假設以I和0分離暗示入棧和出棧操縱.棧的初態(tài)和終態(tài)均為空，入棧和出棧的操

縱序列可暗