《數(shù)據(jù)結(jié)構(gòu)》習題集：第3章棧和隊列

《數(shù)據(jù)結(jié)構(gòu)》習題集：第3章棧和隊列第3章棧和隊列一、選擇題1.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（A）。A、順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)B、散列和索引方式C、鏈表存儲結(jié)構(gòu)和數(shù)組D、線性鏈表結(jié)構(gòu)和非線性存儲結(jié)構(gòu)2.設(shè)棧ST用順序存儲結(jié)構(gòu)表示，則棧ST為空的條件是（B）A、ST.top-ST.base<>0B、ST.top-ST.base==0C、ST.top-ST.base<>nD、ST.top-ST.base==n3.向一個棧頂指針為HS的鏈棧中插入一個s結(jié)點時，則執(zhí)行（C）A、HS->next=s;B、s->next=HS->next；HS->next=s;C、s->next=HS；HS=s;D、s->next=HS；HS=HS->next;4.從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行（C）A、x=HS；HS=HS->next;B、HS=HS->next；x=HS->data;C、x=HS->data；HS=HS->next;D、s->next=Hs；Hs=HS->next;5.表達式a*(b+c)-d的后綴表達式為（B）A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd6.中綴表達式A-（B+C/D）*E的后綴形式是（D）A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-7.一個隊列的入列序列是1，2，3，4，則隊列的輸出序列是（B）A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18.循環(huán)隊列SQ采用數(shù)組空間SQ.base[0,n-1]存放其元素值，已知其頭尾指針分別是front和rear，則判定此循環(huán)隊列為空的條件是（）A、Q.rear-Q.front==nB、Q.rear-Q.front-1==nC、Q.front==Q.rearD、Q.front==Q.rear+19.循環(huán)隊列SQ采用數(shù)組空間SQ.base[0,n-1]存放其元素值，已知其頭尾指針分別是front和rear，則判定此循環(huán)隊列為滿的條件是（）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n10.若在一個大小為6的數(shù)組上實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）A、1，5B、2,4C、4，2D、5，111.用單鏈表表示的鏈式隊列的隊頭在鏈表的（）位置A、鏈頭B、鏈尾C、鏈中12.判定一個鏈隊列Q（最多元素為n個）為空的條件是（）A、Q.front==Q.rearB、Q.front!=Q.rearC、Q.front==(Q.rear+1)%nD、Q.front!=(Q.rear+1)%n13.在鏈隊列Q中，插入s所指結(jié)點需順序執(zhí)行的指令是（）A、Q.front->next=s；f=s;B、Q.rear->next=s；Q.rear=s;C、s->next=Q.rear；Q.rear=s;D、s->next=Q.front；Q.front=s;14.在一個鏈隊列Q中，刪除一個結(jié)點需要執(zhí)行的指令是（）A、Q.rear=Q.front->next;B、Q.rear->next=Q.rear->next->next;C、Q.front->next=Q.front->next->next;D、Q.front=Q.rear->next;15.用不帶頭結(jié)點的單鏈表存儲隊列，其隊頭指針指向隊頭結(jié)點，隊尾指針指向隊尾結(jié)點，則在進行出隊操作時（）A、僅修改隊頭指針B、僅修改隊尾指針C、隊頭尾指針都要修改D、隊頭尾指針都可能要修改。16.棧和隊列的共同點是（）A、都是先進后出B、都是先進先出C、只允許在端點處插入和刪除元素D、沒有共同點17.消除遞歸（）需要使用棧。A、一定B、不一定18.設(shè)有一順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素出棧的順序是s2，s3，s4，s6，s5，s1，則棧的容量至少應(yīng)該是（）A、2B、3C、5D、619.若一個棧的輸入序列是a，b，c，則通過入、出棧操作可能得到a,b,c的不同排列個數(shù)為（）A、4B、5C、6D、720.設(shè)有一順序棧已經(jīng)含有3個元素，如圖3.1所示元素a4正等待進棧。下列不可能出現(xiàn)的出棧序列是（）A、a3,a1,a4,a2B、a3,a2,a4,a1C、a3,a4,a2,a1D、a4,a3,a2,a1圖3.121.鏈棧和順序棧相比，有一個比較明顯的優(yōu)勢是（）A、通常不會出現(xiàn)棧滿的情況B、通常不會出現(xiàn)棧空的情況C、插入操作更容易實現(xiàn)D、刪除操作更加容易實現(xiàn)22.若一個棧的輸入序列是1，2，3，4，…，n，輸出序列的第一個元素是n，則第i個輸出元素是（C）A、不確定B、n-iC、n-i+1D、n-i-123.以下說法正確的是()A、因鏈棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況B、因順序棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況C、對于鏈棧而言,在棧滿狀態(tài)下,如果此時再作進棧運算，則會發(fā)生“上溢”D、對于順序棧而言在棧滿狀態(tài)下如果此時再作進棧運算，則會發(fā)生“下溢”。二、判斷題1.在順序棧棧滿情況下，不能做進棧運算，否則會產(chǎn)生“上溢”。2.鏈棧與順序棧相比的一個優(yōu)點是鏈棧插入和刪除操作更加方便。3.若一個棧的輸入序列為1，2，3，…，n，其輸出序列的第一個元素為n，則其輸出序列的每個元素一定滿足ai=i+1(i=1,2,…,n)。4.在鏈隊列中，即使不設(shè)置尾指針也能進行入隊操作。5.在對鏈隊列（帶頭指針）做出隊操作時，不會改變front指針的值。6.循環(huán)隊列中元素個數(shù)為rear-front。7.一個棧的輸入序列是1,2,3,4，則在棧的輸出序列中可以得到4,3,1,2。8.一個棧的輸入序列是1,2,3,4，則在棧的輸出序列中可以得到1,2,3,4。9.若以鏈表作為棧的存儲結(jié)構(gòu)，則進棧需要判斷棧是否滿。10.若以鏈表作為棧的存儲結(jié)構(gòu)，則出棧需要判斷棧是否空。三、填空題1.棧的特點是（先進后出），隊列的特點是（先進先出）。2.線性表、棧、隊列都是（）結(jié)構(gòu)，可以在線性表的（）位置插入和刪除元素；對于棧只能在（）插入和刪除元素；對于隊列只能在（）插入元素和在（）位置刪除元素。3.有程序如下，則此程序的輸出結(jié)果（棧的元素類型是SelemType為char）是（）。voidmain(){stacks;charx,y;initstack(s);x=’c’;y=’k’;push(s,x);push(s,’a’);push(s,y);pop(s,x);push(s,’t’);push(s,x);pop(s,x);push(s,’s’);while(!stackempty(s)){pop(s,y);printf(y);}printf(x);}4.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是（）。5.向棧中壓入元素的操作是先（）后（）。6.對棧進行退棧操作是先（）后（）。7.用循環(huán)鏈表表示的隊列長度為n，若只設(shè)頭指針，則出隊和入隊的時間復雜度分別是（）和（）；若只設(shè)尾指針，則出隊和入隊的時間復雜度分別是（）和（）。8.從循環(huán)隊列中刪除一個元素時，其操作是（）。9.在一個循環(huán)隊列中，隊首指針指向隊首元素的（）。10.在具有n個單元的循環(huán)隊列中，隊滿時共有（）個元素。11.在HQ的鏈隊列中，判斷只有一個結(jié)點的條件是（）。12.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素a、b、c、d、e、f依次通過棧S，一個元素出棧后即進入隊列Q。若這6個元素出隊列的順序是b、d、c、f、e、a則棧S的容量至少應(yīng)該是（）。13.有程序如下，則此程序的輸出結(jié)果（隊列的元素類型是QSelemType為char）是（）。voidmain(){charx=’e’,y=’c’;enqueue(q,’h’);enqueue(q,’r’);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);enqueue(q,’a’);while(!queueempty(q)){dequeue(q,y);printf(y);}printf(x);}14.有如下遞歸函數(shù)：intdunno(intm){intvalue;if(m==0)value=3;elsevalue=dunno(m-1)+5;return(value);}執(zhí)行語句printf(“%d\n”,dunno(3));的結(jié)果是（）。四、簡答題1.對于堆棧，給出三個輸入項A，B，C，如果輸入項序列為ABC，試給出全部可能的輸出序列，并寫出每種序列對應(yīng)的操作。例如：A進B進C進C出B出A出，產(chǎn)生的序列為CBA。2.簡述以下算法的功能（棧的元素類型是SelemType為int）。（1）statusalgo1(stacks){intI,n,a[255];n=0;while(!stackempty(s)){n++;pop(s,a[n]);}for(I=1;I<=n;I++)push(s,a[I]);}(2)statusalgo2(stacks,inte){stackt;intd;initstack(t);while(!stackempty(s)){pop(s,d);if(d!=e)push(t,d);}while(!stackempty(t)){pop(t,d);push(s,d);}}3.內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從0到m-1）提供給兩個棧s1和s2使用，怎樣分配這部分存儲空間，使得對任一棧僅當這部分空間全滿時才發(fā)生溢出。4.有遞歸過程如下：voidprint(intw){intI;if(w!=0){print(w-1);for(I=1;I<=w;I++)printf(“%3d”,w);printf(“\n”);}}問：調(diào)用語句print(4)的結(jié)果是什么？5.簡述以下算法的功能（棧和隊列的元素類型均為int）voidalgo(queue&q){stacks;intd;initstack(s);while(!queueempty(q)){dequeue(q,d);push(s,d);}while(!stackempty(s)){pop(s,d);enqueue(q,d);}}6.假設(shè)Q[0，9]是一個非循環(huán)線性隊列，初始狀態(tài)為front=rear=0，畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，如果不能入隊，請指出其元素，并說明理由。d,e,b,g,h入隊d,e出隊I,j,k,l,m入隊b出隊n,o,p,q,r入隊。7.按照運算符優(yōu)先數(shù)法，畫出對下面算術(shù)表達式求值時，操作數(shù)棧和運算符棧的變化過程：9-2*4+(8+1)/3。8.設(shè)棧S＝（1，2，3，4，5，6，7），其中7為棧頂元素。寫出調(diào)用algo后棧S的狀態(tài)。voidalgo(Stack*S){inti=0;QueueQ;StackT;InitQueue(Q);InitStack(T);while(!StackEmpty(S)){if(i%2==0)Push(T,Pop(S));elseEnQueue(Q,Pop(S));i++;}while(!QueueEmpty(Q))Push(S,DeQueue(Q));while(!StackEmpty(T))Push(S,Pop(T));}五、設(shè)計題1.回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)2.設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an，試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。3.從鍵盤上輸入一個后綴表達式，試編寫算法計算表達式的值。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：23434+2*$。4.假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。5.假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素站點(注意不設(shè)頭指針)，試編寫相應(yīng)的置空隊、判隊空、入隊和出隊等算法。6.假設(shè)以數(shù)組Q[m]存放循環(huán)隊列中的元素,同時設(shè)置一個標志tag，以tag==0和tag==1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。試編寫與此結(jié)構(gòu)相應(yīng)的插入(enqueue)和刪除(dlqueue)算法。7.如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。要求：①寫出循環(huán)隊列的類型定義；②寫出“從隊尾刪除”和“從隊頭插入”的算法。8.已知Ackermann函數(shù)定義如下:a)①寫出計算Ack(m,n)的遞歸算法，并根據(jù)此算法給出出Ack(2,1)的計算過程。②寫出計算Ack(m,n)的非遞歸算法。9.已知f為單鏈表的表頭指針,鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)下列運算的遞歸算法：①求鏈表中的最大整數(shù)；②求鏈表的結(jié)點個數(shù)；③求所有整數(shù)的平均值。（2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)根據(jù)提示，算法可設(shè)計為：//以下為順序棧的存儲結(jié)構(gòu)定義#defineStackSize100//假定預分配的?？臻g最多為100個元素typedefcharDataType;//假定棧元素的數(shù)據(jù)類型為字符typedefstruct{DataTypedata[StackSize];inttop;}SeqStack;intIsHuiwen(char*t){//判斷t字符向量是否為回文，若是，返回1，否則返回0SeqStacks;inti,len;chartemp;InitStack(&s);len=strlen(t);//求向量長度for(i=0;i<="">Push(&s,t[i]);while(!EmptyStack(&s)){//每彈出一個字符與相應(yīng)字符比較temp=Pop(&s);if(temp!=S[i])return0;//不等則返回0elsei++;}return1;//比較完畢均相等則返回1}（3）設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an，試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。#definemaxsize?？臻g容量voidInOutS(ints[maxsize])//s是元素為整數(shù)的棧，本算法進行入棧和退棧操作。{inttop=0;//top為棧頂指針，定義top=0時為?？?。for(i=1;i<=n;i++)//n個整數(shù)序列作處理。{scanf(“%d”,&x);//從鍵盤讀入整數(shù)序列。if(x!=-1)//讀入的整數(shù)不等于-1時入棧。if(top==maxsize-1){printf(“棧滿\n”);exit(0);}elses[++top]=x;//x入棧。else//讀入的整數(shù)等于-1時退棧。{if(top==0){printf(“?？誠n”);exit(0);}elseprintf(“出棧元素是%d\n”,s[top--])；}}}//算法結(jié)束。（4）從鍵盤上輸入一個后綴表達式，試編寫算法計算表達式的值。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：23434+2*$。[題目分析]逆波蘭表達式(即后綴表達式)求值規(guī)則如下：設(shè)立運算數(shù)棧OPND,對表達式從左到右掃描(讀入)，當表達式中掃描到數(shù)時，壓入OPND棧。當掃描到運算符時，從OPND退出兩個數(shù)，進行相應(yīng)運算，結(jié)果再壓入OPND棧。這個過程一直進行到讀出表達式結(jié)束符$，這時OPND棧中只有一個數(shù)，就是結(jié)果。floatexpr()//從鍵盤輸入逆波蘭表達式，以‘$’表示輸入結(jié)束，本算法求逆波蘭式表達式的值。｛floatOPND[30];//OPND是操作數(shù)棧。init(OPND);//兩棧初始化。floatnum=0.0;//數(shù)字初始化。scanf(“%c”,&x);//x是字符型變量。while(x!=’$’){switch{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’)//拼數(shù)if(x!=’.’)//處理整數(shù){num=num*10+（ord(x)-ord(‘0’)）;scanf(“%c”,&x);}else//處理小數(shù)部分。{scale=10.0;scanf(“%c”,&x);while(x>=’0’&&x<=’9’){num=num+(ord(x)-ord(‘0’)/scale;scale=scale*10;scanf(“%c”,&x);}}//elsepush(OPND,num);num=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é)束switchscanf(“%c”,&x);//讀入表達式中下一個字符。}//結(jié)束while（x！=‘$’）printf(“后綴表達式的值為%f”,pop(OPND));}//算法結(jié)束。[算法討論]假設(shè)輸入的后綴表達式是正確的，未作錯誤檢查。算法中拼數(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ù)。這時對新讀入的字符進入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在結(jié)束處理數(shù)字字符的case后，不能加入break語句。（5）假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。①下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。①A和D是合法序列，B和C是非法序列。②設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。{i=0;//i為下標。j=k=0;//j和k分別為I和字母O的的個數(shù)。while(A[i]!=‘\0’)//當未到字符數(shù)組尾就作。{switch(A[i]){case‘I’:j++;break;//入棧次數(shù)增1。case‘O’:k++;if(k>j){printf(“序列非法\n”)；exit(0);}}i++;//不論A[i]是‘I’或‘O’，指針i均后移。}if(j!=k){printf(“序列非法\n