數據結構棧和隊列練習題及答案

 

一 選擇題

1. 對于棧操作數據的原則是（B ）。

A. 先進先出    B．后進先出      C．后進后出     D． 不分順序

2.一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（ B ）。

A．不確定       B．n-i+1       C． i     D． n-i     

3. 若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（D ）。

A．i-j-1       B．i-j     C．j-i+1       D． 不確定的

4. 若已知一個棧的入棧序列是1,2,3,…,n，其輸出序列為p1,p2,p3，…，pN,若pN是n，則pi是( D )。

A. i     B．n-i     C．n-i+1    D. 不確定

5. 有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ C ）。

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

6. 設棧的輸入序列是1，2，3，4,則（D ）不可能是其出棧序列。

A. 1，2，4，3，      B. 2，1，3，4，    C. 1，4，3，2， 

D. 4，3，1，2，     E. 3，2，1，4，

7. 一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ B ）。

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

8. 設一個棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ D ）。

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

9. 某堆棧的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ D ）。

A. a，c，b，d     B. b, c，d，a     C. c, d，b, a     D. d, c，a，b

10. 設abcdef以所給的次序進棧，若在進棧操作時，允許退棧操作,則下面得不到的序列為（ D ）。

A．fedcba    B. bcafed     C. dcefba    D. cabdef

11. 設有三個元素X，Y，Z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是( C )。

A．XYZ       B. YZX       C. ZXY       D. ZYX

12. 用鏈接方式存儲的隊列，在進行刪除運算時（D ）。

A. 僅修改頭指針      B. 僅修改尾指針       C. 頭、尾指針都要修改       D. 頭、尾指針可能都要修改

13. 用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時( D )。

A．僅修改隊頭指針     B. 僅修改隊尾指針       C. 隊頭、隊尾指針都要修改   D. 隊頭,隊尾指針都可能要修改

14. 遞歸過程或函數調用時，處理參數及返回地址，要用一種稱為（C ）的數據結構。

A．隊列      B．多維數組     C．棧       D. 線性表

 

 

二、判斷題

1. 消除遞歸不一定需要使用棧，此說法（√ ）

2. 棧是實現過程和函數等子程序所必需的結構。（√ ）

3. 兩個棧共用靜態存儲空間，對頭使用也存在空間溢出問題。（√ ）

4．兩個棧共享一片連續內存空間時，為提高內存利用率，減少溢出機會，應把兩個棧的棧底分別設在這片內存空間的兩端。（√ ）

5. 即使對不含相同元素的同一輸入序列進行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（× ）

6. 棧與隊列是一種特殊操作的線性表。（√ ）

7. 若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1. （√ ）

8. 棧和隊列都是限制存取點的線性結構。（ √ ）

9．若輸入序列為1，2，3，4，5，6，則通過一個棧可以輸出序列1，5，4，6，2，3。（× ）

10. 任何一個遞歸過程都可以轉換成非遞歸過程。（√　　）

11. 只有那種使用了局部變量的遞歸過程在轉換成非遞歸過程時才必須使用棧。（× ）

12. 隊列是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結構。（× ）

13. 通常使用隊列來處理函數或過程的調用。（× ）

14. 隊列邏輯上是一個下端和上端既能增加又能減少的線性表。（√ ）

15. 循環隊列通常用指針來實現隊列的頭尾相接。（× ）

16. 循環隊列也存在空間溢出問題。（√ ）

17. 隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算。（× ）

18. 棧和隊列都是線性表，只是在插入和刪除時受到了一些限制。（√ ）

19. 棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方式。（√ ）

 

三、填空 

1．棧是操作受限（或限定僅在表尾進行插入和刪除操作）的線性表，其運算遵循后進先出的原則。

2．棧 是限定僅在表尾進行插入或刪除操作的線性表。

3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是3 1 2。

4．兩個棧共享空間時棧滿的條件兩棧頂指針值相減的絕對值為1（或兩棧頂指針相鄰）。。

5．在作進棧運算時應先判別棧是否滿;在作退棧運算時應先判別棧是否空；當棧中元素為n個，作進棧運算時發生上溢，則說明該棧的最大容量為n。為了增加內存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續的空間時，應將兩棧的棧底 分別設在內存空間的兩端，這樣只有當兩棧頂指針相鄰（即值之差的絕對值為1）時才產生溢出。

6. 多個棧共存時，最好用鏈式存儲結構作為存儲結構。

7．用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的S和X的操作串為S×SS×S×× 。

8. 循環隊列的引入，目的是為了克服假溢出時大量移動數據元素。

9．隊列又稱作先進先出表。

10. 已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s；。

11．區分循環隊列的滿與空，只有兩種方法，它們是犧牲一個存儲單元和設標記。

 

四、應用題

1. 名詞解釋：棧。

答：棧是只準在一端進行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進先出（LIFO）表。

 

2. 名詞解釋：隊列

答：隊列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊尾，允許刪除的一端叫隊頭。最先插入隊的元素最先離開（刪除），故隊列也常稱先進先出（FIFO）表。 

 

3. 什么是循環隊列？

答：用常規意義下順序存儲結構的一維數組表示隊列，由于隊列的性質（隊尾插入和隊頭刪除），容易造成“假溢出”現象，即隊尾已到達一維數組的高下標，不能再插入，然而隊中元素個數小于隊列的長度（容量）。循環隊列是解決“假溢出”的一種方法。通常把一維數組看成首尾相接。在循環隊列下，通常采用“犧牲一個存儲單元”或“作標記”的方法解決“隊滿”和“隊空”的判定問題。 

 

4. 假設以S和X分別表示入棧和出棧操作，則對初態和終態均為空的棧操作可由S和X組成的序列表示（如SXSX）。

（1）試指出判別給定序列是否合法的一般規則。

答：通常有兩條規則。第一是給定序列中S的個數和X的個數相等；第二是從給定序列的開始，到給定序列中的任一位置，S的個數要大于或等于X的個數。

 

 

（2）兩個不同合法序列（對同一輸入序列）能否得到相同的輸出元素序列？如能得到，請舉列說明。

答：可以得到相同的輸出元素序列。例如，輸入元素為A，B，C，則兩個輸入的合法序列ABC和BAC均可得到輸出元素序列ABC。對于合法序列ABC，我們使用本題約定的S×S×S×操作序列；對于合法序列BAC，我們使用SS××S×操作序列。

 

 

5. 有5 個元素，其入棧次序為：A，B，C，D，E，在各種可能的出棧次序中，以元素C，D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？

答：三個：CDEBA，CDBEA，CDBAE 

 

6. 如果輸入序列為1 2 3 4 5 6,試問能否通過棧結構得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6;請說明為什么不能或如何才能得到。

答：輸入序列為123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面4個元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能棧底元素1在棧頂元素2之前出棧。 

   得到135426的過程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變為：13；接著4和5入棧，5，4和2依次出棧，部分輸出序列變為13542；最后6入棧并退棧，得最終結果135426。 

 

7. 若元素的進棧序列為：A、B、C、D、E，運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E？為什么？

答： 能得到出棧序列B、C、A、E、D，不能得到出棧序列D、B、A、C、E。其理由為：若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到D、B、A、C、E出棧序列。 

 

8. 設輸入序列為a,b,c,d,試寫出借助一個棧可得到的兩個輸出序列和兩個不能得到的輸出序列。

答：借助棧結構，n個入棧元素可得到1/(n+1)((2n）！/（n!*n!）)種出棧序列。本題4個元素，可有14種出棧序列，abcd和dcba就是其中兩種。但dabc和adbc是不可能得到的兩種。 

 

9. 設輸入序列為2，3，4，5，6，利用一個棧能得到序列2，5，3，4，6嗎？棧可以用單鏈表實現嗎？

答：不能得到序列2，5，3，4，6。棧可以用單鏈表實現，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設頭結點。 

 

五、算法設計題

1. 設從鍵盤輸入一整數的序列：a1, a2, a3，…，an,試編寫算法實現：用棧結構存儲輸入的整數，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數并出棧。算法應對異常情況（入棧滿等）給出相應的信息。

答：#define maxsize 棧空間容量

     void InOutS(int s[maxsize])

    //s是元素為整數的棧，本算法進行入棧和退棧操作。

        {int top=0; //top為棧頂指針，定義top=0時為棧空。

         for(i=1; i<=n; i++) //n個整數序列作處理。

        {scanf(“%d”,&x); //從鍵盤讀入整數序列。

         if(x!=-1) // 讀入的整數不等于-1時入棧。

        if(top==maxsize-1){printf(“棧滿\n”);exit(0);}else s[++top]=x; //x入棧。

        else //讀入的整數等于-1時退棧。

         {if(top==0){printf(“棧空\n”);exit(0);} else printf(“出棧元素是%d\n”,s[top--])；}}

     }//算法結束。 

 

2. 設表達式以字符形式已存入數組E[n]中，‘#’為表達式的結束符，試寫出判斷表達式中括號（‘（’和‘）’）是否配對的C語言描述算法：EXYX(E); (注：算法中可調用棧操作的基本算法。)

答：[題目分析]判斷表達式中括號是否匹配，可通過棧，簡單說是左括號時進棧，右括號時退棧。退棧時，若棧頂元素是左括號，則新讀入的右括號與棧頂左括號就可消去。如此下去，輸入表達式結束時，棧為空則正確，否則括號不匹配。

     int EXYX(char E[],int n)

     //E[]是有n字符的字符數組，存放字符串表達式，以‘#’結束。本算法判斷表達式中圓括號是否匹配。

     {char s[30]; //s是一維數組，容量足夠大，用作存放括號的棧。

     int top=0; //top用作棧頂指針。

     s[top]= ‘#’; //‘#’先入棧，用于和表達式結束符號‘#’匹配。

     int i=0; //字符數組E的工作指針。

     while(E[i]!= ‘#’) //逐字符處理字符表達式的數組。

          switch(E[i])

     {case‘(’: s[++top]=‘(’; i++ ; break ;

     case‘)’: if(s[top]==‘(’{top--; i++; break;}

          else{printf(“括號不配對”);exit(0);}

          case‘#’: if(s[top]==‘#’){printf(“括號配對\n”);return (1);}

          else {printf(“ 括號不配對\n”);return (0);} //括號不配對

          default : i++; //讀入其它字符，不作處理。

          }

     }//算法結束。

     [算法討論]本題是用棧判斷括號匹配的特例：只檢查圓括號的配對。一般情況是檢查花括號（‘{’，‘}’）、方括號（‘[’，‘]’）和圓括號（‘（’，‘）’）的配對問題。編寫算法中如遇左括號（‘{’，‘[’，或‘（’）就壓入棧中，如遇右括號（‘}’，‘]’，或‘）’），則與棧頂元素比較，如是與其配對的括號（左花括號，左方括號或左圓括號），則彈出棧頂元素；否則，就結論括號不配對。在讀入表達式結束符‘#’時，棧中若應只剩‘#’，表示括號全部配對成功；否則表示括號不匹配。

     另外，由于本題只是檢查括號是否匹配，故對從表達式中讀入的不是括號的那些字符，一律未作處理。再有，假設棧容量足夠大，因此入棧時未判斷溢出。 

 

3. 從鍵盤上輸入一個逆波蘭表達式，用偽碼寫出其求值程序。規定：逆波蘭表達式的長度不超過一行，以$符作為輸入結束，操作數之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：234 34+2*$

答：[題目分析]逆波蘭表達式(即后綴表達式)求值規則如下：設立運算數棧OPND,對表達式從左到右掃描(讀入)，當表達式中掃描到數時，壓入OPND棧。當掃描到運算符時，從OPND退出兩個數，進行相應運算，結果再壓入OPND棧。這個過程一直進行到讀出表達式結束符$，這時OPND棧中只有一個數，就是結果。

     float expr( )

     //從鍵盤輸入逆波蘭表達式，以‘$’表示輸入結束，本算法求逆波蘭式表達式的值。

     ｛float OPND[30]; // OPND是操作數棧。

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

     float num=0.0; //數字初始化。

     scanf (“%c”,&x);//x是字符型變量。

     while(x!=’$’)

     {switch

          {case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼數

               if(x!=’.’) //處理整數

     {num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);}

               else //處理小數部分。

               {scale=10.0; scanf(“%c”,&x);

               while(x>=’0’&&x<=’9’)

               {num=num+(ord(x)-ord(‘0’)/scale;

               scale=scale*10; scanf(“%c”,&x); }

               }//else

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

     case x=‘ ’:break; //遇空格，繼續讀下一個字符。

     case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

     case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

     case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

     case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

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

     }//結束switch

     scanf(“%c”,&x);//讀入表達式中下一個字符。

     }//結束while（x！=‘$’）

     printf(“后綴表達式的值為%f”,pop(OPND));

     }//算法結束。

     [算法討論]假設輸入的后綴表達式是正確的，未作錯誤檢查。算法中拼數部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，認為是數。這種字符的序號減去字符‘0’的序號得出數。對于整數，每讀入一個數字字符，前面得到的部分數要乘上10再加新讀入的數得到新的部分數。當讀到小數點，認為數的整數部分已完，要接著處理小數部分。小數部分的數要除以10（或10的冪數）變成十分位，百分位，千分位數等等，與前面部分數相加。在拼數過程中，若遇非數字字符，表示數已拼完，將數壓入棧中，并且將變量num恢復為0，準備下一個數。這時對新讀入的字符進入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在結束處理數字字符的case后，不能加入break語句。