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

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

2、1=n,p2=n-1,，pi=n-i+1。(3)素的位置,A.數(shù)組Q：n用來表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置,假定隊(duì)列中元素的個(gè)數(shù)小于n,計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為(r-f.(n+f-r)%nC.n+r-fr為隊(duì)尾元)。.(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-dat

3、a;top=top-link；C.x=top;top=top-link；答案：A解釋：x=top-data將結(jié)點(diǎn)的值保存到B.top=top-link;x=top-link；D.x=top-link；中，top=top-link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。(5)設(shè)有一個(gè)遞歸算法如下intfact(intn)/n大于等于0if(n=0)return1;elsereturnn*fact(n-1);則計(jì)算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á)式求值D.前三個(gè)選項(xiàng)都有解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。(7)為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是()。A.隊(duì)列B.棧C.線性表D.有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。(8)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、e3、e4、e5和e6依次進(jìn)入棧S,一個(gè)元素出棧后即進(jìn)入Q,若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和el,則棧S的容量至

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

6、地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V1.n中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚,之后將元素x存儲(chǔ)在Vn。(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)答案：DD.棧解釋：利用棧的后進(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ù)組A0.m中，則入隊(duì)時(shí)的操作為()。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個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。(13)最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear,隊(duì)頭是front,則隊(duì)空的條件是()A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front答案：B解釋：最大容量為n的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n=front,隊(duì)空條件是rear=front。(14)棧和隊(duì)列的共同點(diǎn)是(A.都是先進(jìn)先出B.C.只允許在

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

9、Type*V;intm;棧頂和棧底指針/棧數(shù)組/棧最大可容納元素個(gè)數(shù)DblStack題目分析兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥耍跏紩r(shí)，左棧頂指針為棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。算法描述-1,右棧頂為mo兩(1)棧初始化intInit()S.top0=-1;S.top1=m;return1;/初始化成功入棧操作：intpush(stkS,inti,intx)IIi為棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回if(i1)cout棧號(hào)輸入不對(duì)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代表?xiàng)Ｌ?hào)，i=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素/否則返回-1if(i1)cout棧號(hào)輸入錯(cuò)誤endl；exit(0);switch(i)case0:if(S.top0=-1)cout?？誩ndl；return(-1);elsereturn(S.VS.top0-);case1:if(S.top1=mcout棧空endl;return(-1);else

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

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

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

14、nttop=0;/top為棧頂指針，定義top=0時(shí)為?？?。for(i=1;ix);/從鍵盤讀入整數(shù)序列。if(x!=-1)/讀入的整數(shù)不等于-1時(shí)入棧。if(top=maxsize-1)cout棧滿endl;exit(0);elses+top=x;/x入棧。else/讀入的整數(shù)等于-1時(shí)退棧。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ù)壓入棧，下個(gè)數(shù)初始化casex=:break;/遇空格，繼續(xù)讀下一個(gè)字符。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:/其它符號(hào)不作處理。/結(jié)束switchcinx;/讀入表達(dá)式中下一個(gè)字符。/結(jié)束whil

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

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

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

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

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

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

22、.front-1+M)%M)cout隊(duì)滿endl;exit(0);)Q.dataQ.front=x;/x入隊(duì)列Q.front=(Q.front-1+M)%M;/修改隊(duì)頭指針。/結(jié)束從隊(duì)頭插入算法。(9)已知Ackermann函數(shù)定義如下：+1當(dāng)時(shí)Mkg1,1)當(dāng)時(shí)Aekm1|Aek(mPn1)當(dāng)巾。0遇金口時(shí)寫出計(jì)算Ack(m,n)的遞歸算法，并根據(jù)此算法給出出Ack(2,1)的計(jì)算過程。寫出計(jì)算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)的計(jì)算過程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