數(shù)據(jù)結(jié)構(gòu)C語言版第二版(嚴蔚敏)第3章棧和隊列答案

1、第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)若已知一個棧的入棧序列是p1=n，則pi為()。1,2,3,，n,其輸出序列為p1p2,p3,，pn,若A.i.n-i+1答案：C解釋：棧是后進先出的線性表，一個棧的入棧序列是1,2,3,一個元素為n,說明1,2,3,，n一次性全部進棧，再進行輸出，所以n,而輸出序列的第p

2、1=n,p2=n-1,，pi=n-i+1。(3)素的位置,A.數(shù)組Q：n用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置,假定隊列中元素的個數(shù)小于n,計算隊列中元素個數(shù)的公式為(r-f.(n+f-r)%nC.n+r-fr為隊尾元)。.(n+r-f)%n答案：D解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度,而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE(本題為n),然后與MAXSIZE(本題為n)求余,即(n+r-f)%n(4)鏈式棧結(jié)點為：(data,link)top指向棧頂.若想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中，則應(yīng)執(zhí)行操作()。A.x=top-dat

3、a;top=top-link；C.x=top;top=top-link；答案：A解釋：x=top-data將結(jié)點的值保存到B.top=top-link;x=top-link；D.x=top-link；中，top=top-link棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。(5)設(shè)有一個遞歸算法如下intfact(intn)/n大于等于0if(n=0)return1;elsereturnn*fact(n-1);則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為(A.n+1B.n-1)。C.nD.n+2答案：A解釋：特殊值法(6)棧在()A遞歸調(diào)用答案：D設(shè)n=0,易知僅調(diào)用一次fact(n)函數(shù)，故選A。

4、中有所應(yīng)用。B.函數(shù)調(diào)用C.表達式求值D.前三個選項都有解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧的后進先出性質(zhì)。(7)為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是()。A.隊列B.棧C.線性表D.有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。(8)設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次進入棧S,一個元素出棧后即進入Q,若6個元素出隊的序列是e2、e4、e3、e6、e5和el,則棧S的容量至

5、少應(yīng)該是()。A.2B.3C.4D.6答案：B解釋：元素出隊的序列是e2、e4、e3、e6、e5和el,可知元素入隊的序列是e2、e4、e3、e6、e5和el,即元素出棧的序列也是e2、e4、e3、e6、e5和el,而元素el、e2、e3、e4、e5和e6依次進入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。(9)若一個棧以向量V1.n存儲，初始棧頂指針top設(shè)為n+1,則元素x進棧的正確操作是(VA.top+;Vtop=x;B.Vtop=x;top+;C. top-; Vtop=x;答案：CD. Vtop=x; top-;解釋：初始棧頂指針top為n+1,說明元素從數(shù)組向量的高端

6、地址進棧，又因為元素存儲在向量空間V1.n中，所以進棧時top指針先下移變?yōu)閚,之后將元素x存儲在Vn。(10)設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用()數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲結(jié)構(gòu)B.隊列C.線性表的鏈式存儲結(jié)構(gòu)答案：DD.棧解釋：利用棧的后進先出原則。(11)用鏈接方式存儲的隊列，在進行刪除運算時()。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。(12)循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為()。A.r

7、ear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D解釋：數(shù)組A0.m中共含有m+1個元素，故在求模運算時應(yīng)除以m+1。(13)最大容量為n的循環(huán)隊列，隊尾指針是rear,隊頭是front,則隊空的條件是()A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front答案：B解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n=front,隊空條件是rear=front。(14)棧和隊列的共同點是(A.都是先進先出B.C.只允許在

8、端點處插入和刪除元素答案：CD.都是先進后出沒有共同點解釋：棧只允許在棧頂處進行插入和刪除元素,隊列只允許在隊尾插入元素和在隊頭刪除元素。(15)一個遞歸算法必須包括(A.遞歸部分C.迭代部分答案：B)。B.D.終止條件和遞歸部分終止條件和迭代部分2.算法設(shè)計題(1)將編號為0和1的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。第0號棧的棧頂指針top0等于-1時該棧為空，當?shù)?號棧的棧頂指針top1等于m時該棧為空。兩個棧均從兩端向中間增長雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：試編寫雙棧初始化，判斷?？?、棧滿、進棧和出棧等算法的函數(shù)。Typedefstructinttop2,bot2;SElem

9、Type*V;intm;棧頂和棧底指針/棧數(shù)組/棧最大可容納元素個數(shù)DblStack題目分析兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時，左棧頂指針為棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。算法描述-1,右棧頂為mo兩(1)棧初始化intInit()S.top0=-1;S.top1=m;return1;/初始化成功入棧操作：intpush(stkS,inti,intx)IIi為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回if(i1)cout棧號輸入不對endl;exit(0);if(S.top1-S.top0=1)cout棧已滿endl;retu

10、rn(0);switch(i)case0:S.V+S.top0=x;return(1);break;case1:S.V-S.top1=x;return(1);IIpush退棧操作ElemTypepop(stkS,inti)/退棧。i代表棧號，i=0時為左棧，i=1時為右棧。退棧成功時返回退棧元素/否則返回-1if(i1)cout棧號輸入錯誤endl；exit(0);switch(i)case0:if(S.top0=-1)cout?？誩ndl；return(-1);elsereturn(S.VS.top0-);case1:if(S.top1=mcout?？誩ndl;return(-1);else

11、return(S.VS.top1+);IIswitchII算法結(jié)束(4)判斷?？読ntEmpty();return(S.top0=-1&S.top1=m);算法討論請注意算法中兩棧入棧和退棧時的棧頂指針的計算。左棧是通常意義下的棧，而右棧入棧操作時，其棧頂指針左移(減1),退棧時，棧頂指針右移(加1)。(2)回文是指正讀反讀均相同的字符序列，如abba和abdba”均是回文，但good不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)題目分析將字符串前一半入棧，然后，棧中元素和字符串后一半進行比較。即將第一個出棧元素和后一半串中第一個字符比較，若相等，則再出棧一個元素

12、與后一個字符比較，直至?？?，結(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時，結(jié)論字符序列不是回文。算法描述#defineStackSize100/假定預(yù)分配的?？臻g最多為100個元素typedefcharDataType;/假定棧元素的數(shù)據(jù)類型為字符typedefstructDataTypedataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/判斷t字符向量是否為回文，若是，返回1,否則返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);/求向量長度for(i=0;ilen/2

13、;i+)/將一半字符入棧Push(&s,ti);while(!EmptyStack(&s)/每彈出一個字符與相應(yīng)字符比較temp=Pop(&s);if(temp!=Si)return0;/不等則返回0elsei+;return1;/比較完畢均相等則返回1(3)設(shè)從鍵盤輸入一整數(shù)的序列：ai,a2,a3,，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當aiw-i時，將a進棧；當ai=-i時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況(入棧滿等)給出相應(yīng)的信息。算法描述#definemaxsize棧空間容量voidInOutS(intsmaxsize)/s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。i

14、nttop=0;/top為棧頂指針，定義top=0時為?？?。for(i=1;ix);/從鍵盤讀入整數(shù)序列。if(x!=-1)/讀入的整數(shù)不等于-1時入棧。if(top=maxsize-1)cout棧滿endl;exit(0);elses+top=x;/x入棧。else/讀入的整數(shù)等于-1時退棧。if(top=0)cout?？誩ndl;exit(0);elsecout“出棧元素是stop-x;/x是字符型變量。while(x!=$)switchcase，0，=x=0&xx;else/處理小數(shù)部分。scale=10.0;cinx;while(x=0&xx;/elsepush(OPND,num);n

15、um=0.0;/數(shù)壓入棧，下個數(shù)初始化casex=:break;/遇空格，繼續(xù)讀下一個字符。casex=+:push(OPND,pop(OPND)+pop(OPND);break;casex=-:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;casex=*:push(OPND,pop(OPND)*pop(OPND);break;casex=/:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;default:/其它符號不作處理。/結(jié)束switchcinx;/讀入表達式中下一個字符。/結(jié)束whil

16、e(x!=$)cout后綴表達式的值為j)入棧次數(shù)增1cout “序列非法ednl ； exit(0);if(j!=k)cout“序列非法endl；return(false);elsecout“序歹U合法rear=Q-rear-next;/將隊尾指針指向頭結(jié)點while(Q-rear!=Q-rear-next)/當隊列非空，將隊中元素逐個出隊s=Q-rear-next;Q-rear-next=s-next;deletes;/回收結(jié)點空間(2)判隊空intEmptyQueue(LinkQueue*Q)判隊空。當頭結(jié)點的next指針指向自己時為空隊returnQ-rear-next-next=Q-

17、rear-next;(3)入隊voidEnQueue(LinkQueue*Q,Datatypex)/入隊。也就是在尾結(jié)點處插入元素QueueNode*p=newQueueNode;/申請新結(jié)點p-data=x;p-next=Q-rear-next;/初始化新結(jié)點并鏈入Q-rear-next=p;Q-rear=p;/將尾指針移至新結(jié)點(4)出隊DatatypeDeQueue(LinkQueue*Q)/出隊，把頭結(jié)點之后的元素摘下Datatypet;QueueNode*p;if(EmptyQueue(Q)Error(Queueunderflow);p=Q-rear-next-next;/p指向?qū)⒁?/p>

18、摘下的結(jié)點x=p-data;/保存結(jié)點中數(shù)據(jù)if(p=Q-rear)/當隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點Q-rear=Q-rear-next;Q-rear-next=p-next;elseQ-rear-next-next=p-next;/摘下結(jié)點pdeletep;/釋放被刪結(jié)點returnx;(7)假設(shè)以數(shù)組Qm存放循環(huán)隊列中的元素，同時設(shè)置一個標志tag,以tag=0和tag=1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為空還是滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。算法描述(1)初始化SeQueueQ

19、ueueInit(SeQueueQ)/初始化隊列Q.front=Q.rear=0;Q.tag=0;returnQ;(2)入隊SeQueueQueueIn(SeQueueQ,inte)/入隊列if(Q.tag=1)&(Q.rear=Q.front)cout隊列已滿endl;elseQ.rear=(Q.rear+1)%m;Q.dataQ.rear=e;if(Q.tag=0)Q.tag=1;/隊列已不空returnQ;(3)出隊ElemTypeQueueOut(SeQueueQ)/出隊列if(Q.tag=0)cout隊列為空endl;exit(0);elseQ.front=(Q.front+1)%m

20、;e=Q.dataQ.front;if(Q.front=Q.rear)Q.tag=0;/空隊歹Ureturn(e);(8)如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求：寫出循環(huán)隊列的類型定義；寫出“從隊尾刪除”和“從隊頭插入”的算法。題目分析用一維數(shù)組v0.M-1實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針front和隊尾指針rear,約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，(rear+1)%m=front為隊滿。約定隊頭端入隊向下標小的方向發(fā)展，隊尾端入隊向下標大的方向發(fā)展。算法描述#defineM隊列可能達到的最大長度typed

21、efstructelemtpdataM;intfront,rear;cycqueue;elemtpdelqueue(cycqueueQ)/Q是如上定義的循環(huán)隊列，本算法實現(xiàn)從隊尾刪除，若刪除成功，返回被刪除元素，否則隊歹ij空endl； exit(0);修改隊尾指針。返回出隊元素。給出出錯信息。if(Q.front=Q.rear)coutQ.rear=(Q.rear-1+M)%M;/return(Q.data(Q.rear+1+M)%M);/從隊尾刪除算法結(jié)束voidenqueue(cycqueueQ,elemtpx)/Q是順序存儲的循環(huán)隊列，本算法實現(xiàn)“從隊頭插入元素if(Q.rear=(Q

22、.front-1+M)%M)cout隊滿endl;exit(0);)Q.dataQ.front=x;/x入隊列Q.front=(Q.front-1+M)%M;/修改隊頭指針。/結(jié)束從隊頭插入算法。(9)已知Ackermann函數(shù)定義如下：+1當時Mkg1,1)當時Aekm1|Aek(mPn1)當巾。0遇金口時寫出計算Ack(m,n)的遞歸算法，并根據(jù)此算法給出出Ack(2,1)的計算過程。寫出計算Ack(m,n)的非遞歸算法。算法描述intAck(intm,n)if(m=0)return(n+1);elseif(m!=0&n=0)return(Ack(m-1,1);elsereturn(Ack(m-1,Ack(m,m-1);/算法結(jié)束Ack(2,1)的計算過程Ack(2,1)=Ack(1,Ack(2,0)/=Ack(1,Ack(1,1)/=Ack(1,Ack(0,Ack(1,0)/=Ack(1,Ack(0,Ack(0,1)/=Ack(1,Ack(0,2)/=Ack(1,3)/=Ack(0,Ac