第3章棧和隊列

1、數(shù)據(jù)結構第3章 棧和隊列 共85題一、單選1. (1)分     題目ID號：10705     題目難度：容易    設對一組數(shù)據(jù)的處理具有“后進先出”的特點，則應采用的數(shù)據(jù)結構是【1】    A. 隊列     B. 棧    C. 順序表    

2、;D. 二叉樹題目答案：B2. (1)分     題目ID號：10706     題目難度：容易    若進棧序列為3、5、7、9，進棧和出棧可穿插進行，則不可能的出棧序列是【1】    A. 7，5，3，9      B. 9，5，7，3      

3、0;C. 9，7，5，3      D. 7，5，9，3題目答案：B3. (1)分     題目ID號：10707     題目難度：較難    設用一維數(shù)組Am存儲棧，令Am-1為棧底，t指示當前棧頂?shù)奈恢?。如果棧不空，則出棧時應使【1】    A. t=t+l    

4、0;  B. t=t-1        C. t=m-1      D. 不改變t題目答案：A4. (1)分     題目ID號：10708     題目難度：容易    設用一維數(shù)組Am存儲棧，令A0為棧底，top指示當前錢頂?shù)奈恢?，當把棧清空時所要執(zhí)行的操

5、作是【1】    A. top-    B. top=0    C. top=-1   D. top=m-1題目答案：C5. (1)分     題目ID號：10709     題目難度：容易    設棧s的初始狀態(tài)為空，如果進棧序列為1、2、3、4、5、6，出

6、棧序列為3、2、5、6、4、1，則s的容量至少是【1】     A. 6     B. 4    C. 2    D. 3題目答案：D6. (1)分     題目ID號：10710     題目難度：容易    設棧s最多能容納4

7、個元素，現(xiàn)有A、B、C、D、E、F六個元素按順序進棧，以下可能的出棧序列是【1】    A. E、D、C、B、A、F       B. B、C、E、F、A、D    C. C、B、E、D、A、F       D. A、D、F、E、B、C題目答案：C7. (1)分     題目ID

8、號：10711     題目難度：容易    鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是【1】    A. 插入操作更加方便           B. 通常不會出現(xiàn)棧滿的情況    C. 不會出現(xiàn)?？盏那闆r       &

9、#160; D. 刪除操作更加方便題目答案：B8. (1)分     題目ID號：10712     題目難度：容易    在完成出棧操作時，【1】    A. 必須判斷棧是否滿         B. 要判斷棧元素的類型    C.

10、0;必須判斷棧是否空         D. 不必做任何判斷題目答案：C9. (1)分     題目ID號：10713     題目難度：容易    已知棧的入棧序列是1、2、3、n，出棧序列是e1、e2、en。若e1=n，則ei為【1】    A. i    

11、 B. n-i+1      C. n-i      D. 不能確定題目答案：B10. (1)分     題目ID號：10714     題目難度：容易    在解決計算機主機與打印機之間速度不匹配問題時，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，打印機則從該緩沖區(qū)取

12、出數(shù)據(jù)打印，該緩沖區(qū)應該是一個【1】結構。     A. 棧        B. 隊列       C. 線性表    D. 數(shù)組題目答案：B11. (1)分     題目ID號：10715     題目難度：

13、容易    【1】不是隊的基本運算。     A. 向隊尾插入一個元素           B. 讀隊頭元素     C. 刪除隊中第i個元素            D. 判隊是否為空題目答

14、案：C12. (1)分     題目ID號：10716     題目難度：容易    當以順序方式存儲隊列時，解決“假溢出”較為有效的方法是采用【1】    A. 順序隊列     B. 鏈式隊列      C. 順序循環(huán)隊列   

15、0;  D. 三種都可以題目答案：C13. (1)分     題目ID號：10717     題目難度：容易    設一維數(shù)組Qm用于存放循環(huán)隊列中的元素，同時用f指示當前隊頭元素的位置，r指示當前隊尾元素的下一個位置。假定隊中元素個數(shù)總小于m，則計算隊列中元素個數(shù)的公式為【1】    A. (m+r-f)m     

16、 B. r-f      C. m-(f-r)     D. (m+(f-r)m題目答案：A題目分析：循環(huán)隊列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的求元素個數(shù)的運算可以利用求模運算。14. (1)分     題目ID號：10718     題目難度：容易    若用一個大小為

17、10的一維數(shù)組存儲順序循環(huán)隊列，且當前rear和front的值分別為4和8，當從隊列中刪除3個元素再加入2個元素后，rear和front的值分別是【1】    A. 無法完成要求的操作     B. 6和l     C. 7和0     D.  6和11題目答案：B題目分析：循環(huán)隊列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加1運算通常用

18、求模運算來實現(xiàn)。所以入隊和出隊時的操作分別為：rear=(rear+1)%m，front=(front+1)%m。15. (1)分     題目ID號：10719     題目難度：容易    棧和隊列都是運算受限的線性表，它們的共同點是【1】    A. 只允許在端點處插入和刪除元素      B. 元素都是后進先出 

19、;   C. 元素都是先進先出                  D. 必須采用順序存儲結構題目答案：A題目分析：棧和隊列都是運算受限的線性表，只允許在表端點處進行操作。16. (1)分     題目ID號：11091     題目難度：容易 

20、60;  在一個鏈式隊列中，假設front和rear分別為隊頭和隊尾指針，則插入s所指結點的操    作為【1】    A. rear->next=s;rear=s;              B. front->next=s;front=s;    C. s->next

21、=front;front=s;            D. s->next=rear;rear=s;題目答案：A題目分析：隊列是運算受限的線性表（FIFO），插入元素只能插在隊尾，所以需修改隊尾指針。17. (1)分     題目ID號：11096     題目難度：容易    用鏈接方式存儲的隊列，在進行刪除運

22、算時【1】    A. 僅修改頭指針                B. 頭、尾指針可能都要修改    C. 頭、尾指針都要修改          D. 僅修改尾指針題目答案：B題目分析：若隊列中的元素多于一個，刪除隊列

23、中的隊尾元素，只需修改隊尾指針；若隊列中只有一個元素，刪除該元素后，隊頭隊尾指針都需要修改。18. (1)分     題目ID號：11097     題目難度：容易    設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用【1】數(shù)據(jù)結構最佳。    A. 線性表的順序存儲結構       B. 隊列 &#

24、160;  C. 線性表的鏈式存儲結構       D. 棧題目答案：D19. (1)分     題目ID號：11099     題目難度：容易    表達式a*(b+c)-d的后綴表達式是【1】    A. abcd*+-     B.&

25、#160;abc+*d-    C. abc*+d-     D. -+*abcd題目答案：B20. (1)分     題目ID號：11228     題目難度：容易    已知隊列(4，41，5，7，1826，15)，第一個進入隊列的元素是4，則第五個出隊列的元素是【1】     A.&

26、#160;5       B. 41       C. 18        D. 7題目答案：C21. (1)分     題目ID號：11229     題目難度：容易    對于順序存儲的循環(huán)隊列，

27、存儲空間大小為N，頭指針為F，尾指針為R，隊列中元素的個數(shù)應為【1】    A. R-F   B. N+R-F  C. (RF十1)N   D. (N+R-F)%N題目答案：D22. (1)分     題目ID號：11230     題目難度：容易    一個隊列的進隊列順序是1，2，3，

28、4，則出隊列順序為【1】    A. 4,3,2,1    B. 2,4,3,1    C. 1,2,3,4    D. 3,2,1,4題目答案：C23. (1)分     題目ID號：11231     題目難度：容易    下列關于棧的敘述中正確

29、的是【1】    A. 在棧中只能插入數(shù)據(jù)    B. 在棧中只能刪除數(shù)據(jù)    C. 棧是先進先出的線性表  D. 棧是先進后出的線性表題目答案：D24. (1)分     題目ID號：11232     題目難度：容易    設棧S和隊列Q的初始狀態(tài)為空，元素e1，

30、e2，e3，e4，e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1,則棧S的容量至少應該是【1】    A. 6          B. 4          C. 3        

31、0; D. 2題目答案：C題目分析：根據(jù)棧的性質(zhì)（LIFO）得，e2出棧前，棧中存有e1和e2兩個元素，e4出棧前，棧中存有e1、e3和e4三個元素，e4和e3出棧以后，e5和e6入棧，棧中同樣存在e1、e5和e6三個元素，然后三個元素依次出棧，所以棧的容量至少應該為3。25. (1)分     題目ID號：11651     題目難度：容易    若一個棧以向量V1.n存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作

32、是【1】    A. top=top+1;  Vtop=x             B. Vtop=x; top=top+1    C. top=top-1;  Vtop=x           &#

33、160; D. Vtop=x; top=top-1題目答案：C題目分析：棧式運算受限的線性表，只允許在棧頂進行插入和刪除操作。本題中棧頂指針為n+1，該數(shù)組將棧頂放在了下標大的一端，所以在進行入棧操作時top指針應該進行減一操作。通常元素進棧的操作為：先移動棧頂指針后存入元素。26. (1)分     題目ID號：11652     題目難度：容易    一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第

34、i（1in）個元素是【1】    A. 不確定          B. n-i+1          C. i           D. n-i題目答案：B題目分析：【解析】根據(jù)棧的性質(zhì)（LIFO），若輸出的第

35、一個元素是n，則表明所有的元素已經(jīng)入棧，則出棧順序為n，n-1， ，3，2，1。27. (1)分     題目ID號：11653     題目難度：容易    如果我們用數(shù)組A1.100來實現(xiàn)一個大小為100的棧，并且用變量top來指示棧頂，top的初值為0，表示?？?。請問在top為100時，再進行入棧操作，會產(chǎn)生【1】    A. 正常動作    

36、;  B. 溢出      C. 下溢      D. 同步題目答案：B題目分析：當top為100時，表示棧已經(jīng)滿了，此時再進行入棧操作，則會造成溢出。28. (1)分     題目ID號：11654     題目難度：容易    棧在【1】中應用。  

37、60; A. 遞歸調(diào)用        B. 子程序調(diào)用       C. 表達式求值    D. A,題目答案：D29. (1)分     題目ID號：11655     題目難度：容易    若用一個大小為6

38、的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？【1】    A. 1和 5         B. 2和4          C. 4和2        

39、 D. 5和1題目答案：B題目分析：循環(huán)隊列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加1運算通常用求模運算來實現(xiàn)。所以入隊和出隊時的操作分別為：rear=(rear+1)%m，front=(front+1)%m。30. (1)分     題目ID號：11656     題目難度：容易    棧和隊列的共同點是【1】    A. 都是先進先出 &#

40、160;                      B. 都是先進后出    C. 只允許在端點處插入和刪除元素        D. 沒有共同點題目答案：C題目分析：棧和隊列都是運算受限的線性表，只允許在表端點處進行操作。31.&

41、#160;(1)分     題目ID號：11657     題目難度：容易    判定一個棧S（元素個數(shù)最多為MAXSIZE）為空和滿的條件分別為【1】    A. S->top!=-1   S->top!=MAXSIZE-1    B. S->top=-1    S-&

42、gt;top=MAXSIZE-1    C. S->top=-1    S->top!=MAXSIZE-1    D. S->top!=-1   S->top=MAXSIZE-1題目答案：B二、多選1. (1)分     題目ID號：11227     題目難度：容易  &#

43、160; 已知元素(8，25，14，87，51，90，6，19，20)。這些元素以怎樣的順序進入棧；才能使出棧的順序滿足：8在51前面；90在87后面；20在14后面；25在6前面；19在90后面【1】    A. 20,6,8,51,90,25,14,19,87    B. 51,6,19,20,14,8,87,90,25    C. 19,20,90,8,6,25,51,14,87    D.

44、 6,25,51,8,20,19,90,87,14題目答案：BCD三、是非1. (1)分     題目ID號：11233     題目難度：容易    【1】棧和隊列邏輯上都是線性表。題目答案：T2. (1)分     題目ID號：11234     題目難度：容易    【1】采用循環(huán)鏈

45、表作為存儲結構的隊列就是循環(huán)隊列。題目答案：F3. (1)分     題目ID號：11235     題目難度：容易    【1】棧和隊列都是順序存取的線性表，但它們對存取位置的限制不同。題目答案：T4. (1)分     題目ID號：11236     題目難度：容易    【1】在棧中只能插入數(shù)

46、據(jù)。題目答案：F5. (1)分     題目ID號：11237     題目難度：容易    【1】在棧滿情況下不能做進棧運算，否則產(chǎn)生“上溢”。題目答案：T6. (1)分     題目ID號：11238     題目難度：容易    【1】判定一個隊列q(最多元素為m)為空的條件是(q一rear十

47、1)mq一front.題目答案：F四、填空1. (3)分     題目ID號：10746     題目難度：容易    一個理發(fā)店有兩名理發(fā)師，一名理發(fā)師專為年紀最大的顧客服務，另一名理發(fā)師為進入理發(fā)店時間最長的顧客服務，進入理發(fā)店的顧客根據(jù)到達的時間先后順序都排人一個隊列。假設用程序來模擬理發(fā)店顧客隊列的變化情況，該顧客隊列在邏輯上可視為哪種數(shù)據(jù)結構?【1】要存儲相關信息應采用哪一種存儲結構?【2】為什么?【3】題目答案：線性表】鏈式存儲結構】

48、因為顧客出隊沒有限定在一端；新來的顧客要加入隊列，接受理發(fā)師服務的顧客要離開隊列，對顧客隊列這個線性表來說，需要經(jīng)常的插入和刪除操作。】2. (2)分     題目ID號：10782     題目難度：容易    在以順序方式存儲隊列時，會出現(xiàn)“假溢出”現(xiàn)象，請解釋這一現(xiàn)象【1】，并說明解決“假溢出”的方法及其原理?！?】題目答案：“假溢出”是指存儲隊列的空間中還有空余，但不能進行入隊操作，它是由隊列的操作方式?jīng)Q定的。】解決“假溢出”的方法有：建

49、立一個足夠大的存儲空間，但這樣會造成空間的浪費。采用循環(huán)隊列方式。把存儲隊列的一維空間看成是一個首尾相接的圓環(huán)，這樣就可以實現(xiàn)對由于元素出隊而空出來的空間的循環(huán)使用。采用平移元素的方法。每當出現(xiàn)“假溢出”時，將隊列中所有元素平移，使當前隊頭元素位于數(shù)組的最前端，并修改隊頭和隊尾指示器。此方法效率很低?！?. (5)分     題目ID號：10785     題目難度：較難    有n個人排成一排，每個人的編號為i(0in)，現(xiàn)讓這n個人從左到右1

50、、2、l、2、報數(shù)，凡報“1”的人出列，報“2”的人立即站到隊的最右端，此過程反復進行，直到n個人都已出列。設已知n個人原來在隊列中的順序，以下程序可求出他們出列的順序。例如，設n6，韌始順序為1、2、3、4、5、6，則出列順序為1、3、5、2、6、4。    算法說明：此問題可利用隊列結構處理。設一維數(shù)組Pn存放循環(huán)隊列，f和r分別為隊列的隊頭和隊尾指示器，首先讓n個人的初始序號依次入隊，然后反復執(zhí)行以下操作，直到隊列為空。    輸出隊頭元素，并刪除之：    若剛剛離隊

51、的元素值在當時的隊列中最大，則記錄下當前隊列中最大元素值，否則將隊頭元素插入到隊尾。    程序如下：    #include<iostream    using std:cout;    using std:endl;    const int N20；    int main( )

52、0;   int pN;    int f0，r0，qmN;    for(int i1;i<N;i十十)      p 【1】 i;      r=(r十1)N;        do    &

53、#160;  int t=pf;       cout<<t<<”  ”;       f 【2】   ；       if(tqm)qm-;       else   

54、60;   【3】 pf;       r   【4】        f   【5】             while(f!r);     cout<<en

55、dl：     return 0;    題目答案：r】(f+1)%N 】pr】(r+1)N】(f+1)N】4. (5)分     題目ID號：10791     題目難度：較難    以下函數(shù)用于檢驗一個表達式中括號是否匹配。如果匹配返回1，否則返回0。設表達式中只使用了括號( )和方括號 ，表達式在一維數(shù)組exp中

56、。    算法說明：為檢查表達式中括號的匹配情況，可設置一個棧s。從左到右掃描表達式，若當前字符為左括號，則將其壓入棧s中。若當前字符為右括號，則檢查它是否與棧頂?shù)淖罄ㄌ栂嗥ヅ?。若相匹配，則刪去這一對括號；不相匹配，則表示表達式中括號不匹配。若掃描完表達式時棧為空，則說明表達式中括號是匹配的，否則是不匹配的。函數(shù)中使用變量flag作為括號匹配的標志，flag為1表示匹配，flag為0表示不匹配。程序如下：  const int MaxSize=100;  int matching(ch

57、ar expMaxSize)    char sMaxSize;    int top=-1;        /s作為順序棧，top為棧頂指示器    int flag,i;    flag=1;i=0;    while(expi&&flag) 

58、60;    switch(expi)        case'(':        case'':           【1】=expi;break;        case&

59、#39;)':           if(【2】)top-;           else flag=0;           break;        case'

60、;':           if(【3】)top-;           else flag=0;           break;          

61、  【4】        if(【5】)return 1;    else return 0;  題目答案：s+top】top!=-1&&stop='('】top!=-1&&stop=''】i+】flag&&top=-1】5. (3)分     題目ID號：10796&

62、#160;    題目難度：較難    編寫一個函數(shù)，利用隊列和棧的基本運算將指定隊列中的元素進行逆轉(zhuǎn)。    算法說明：利用一個臨時棧tempst，將指定隊列que中所有元素出隊并入棧到tempst，然后再將棧tempst中的所有元素出棧并入隊到que，此時，隊列que中的元素已發(fā)生逆轉(zhuǎn)。在以下函數(shù)中使用了STL的容器適配器定義隊列和棧。    程序如下：    #include &l

63、t;queue>    #include <stack>    using namespace std;    template <typename T>    void reverse_que(quedu<T> &que)      T x;

64、60;     stack<T> tempst;      while(  【1】  )        x=que.front();                  

65、 /取隊頭元素到x        tempst.push(x);                  /x入棧        【2】          

66、     while(!tempst.empty()             /當棧不為空時        x=tempst.top();                 

67、;  /取棧頂元素到x        【3】           tempst.pop();                     /出棧   &#

68、160;      題目答案：!que.empty()】que.pop()】que.push(x)】6. (1)分     題目ID號：11104     題目難度：容易    循環(huán)隊列的引入，目的是為了克服【1】題目答案：假溢出時大量移動數(shù)據(jù)元素】7. (1)分     題目ID號：11105   

69、;  題目難度：容易    順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是【1】題目答案：data+top=x;】8. (1)分     題目ID號：11110     題目難度：容易    棧的特點是【1】題目答案：先進后出FILOLIFO】9. (1)分     題目ID號：11142 

70、;    題目難度：容易    隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是【1】題目答案：先進先出FIFO】10. (5)分     題目ID號：11145     題目難度：容易有n個人排成一排，每個人的編號為i(0in)，現(xiàn)讓這n個人從左到右1、2、l、2、報數(shù)，凡報“1”的人出列，報“2”的人立即站到隊的最右端，此過程反復進行，直到n個人都已出列。設已知n個人原來在隊列中的

71、順序，以下程序可求出他們出列的順序。例如，設n6，韌始順序為1、2、3、4、5、6，則出列順序為1、3、5、2、6、4。    算法說明：此問題可利用隊列結構處理。設一維數(shù)組Pn存放循環(huán)隊列，f和r分別為隊列的隊頭和隊尾指示器，首先讓n個人的初始序號依次入隊，然后反復執(zhí)行以下操作，直到隊列為空。    輸出隊頭元素，并刪除之：    若剛剛離隊的元素值在當時的隊列中最大，則記錄下當前隊列中最大元素值，否則將隊頭元素插入到隊尾。    程

72、序如下：    #include<iostream    using std:cout;    using std:endl;    const int N20；    int main( )    int pN;    int f0

73、，r0，qmN;    for(int i1;i<N;i十十)      p 【1】 i;      r=(r十1)N;        do       int t=pf;      

74、 cout<<t<<”  ”;       f 【2】   ；       if(tqm)qm-;       else       【3】 pf;     

75、0; r   【4】        f   【5】             while(f!r);     cout<<endl：     return 0;題目答案：r】(f+1)%N】pr】(r

76、+1)N 】(f+1)N】11. (3)分     題目ID號：11146     題目難度：容易    以下函數(shù)的功能是，將一維整型數(shù)組A中所有奇數(shù)移到所有偶數(shù)之前。算法說明：可以設置兩個下標變量i和j，它們的初值分別為0和n1。從數(shù)組的兩端開始，讓i向右j向左對數(shù)組中元素進行掃描，若Ai為偶數(shù)，Aj為奇數(shù)，則交換Ai和Aj。當i和i重合時，算法結束。    程序如下：  &

77、#160; void oddbefore(int A ,int n)    int i,j,t;    iO；jn一1;    while(i<j)      while(Ai21 【1】 )    /Ai為奇數(shù)時，i向右掃描     

78、0;  i+;      while(Aj20 【2】 )    /Aj為偶數(shù)時，j向左掃描        j-;      if(  【3】  )        tAi;Ai=Aj;Aj=t;

79、60;     i+;j-;            題目答案：i < j】i < j】i < j】12. (5)分     題目ID號：11219     題目難度：容易    線性表、棧和隊列都是【1

80、】結構，可以在線性表的【2】位置插入和刪除元素，對于棧只能在【3】位置插人和刪除元素，對于隊列只能在【4】位置插人和【5】位置刪除元素。題目答案：線性】任意】棧頂】隊尾】隊頭】13. (2)分     題目ID號：11220     題目難度：容易    對于順序存儲的棧，因為棧的空間是有限的，在進行【1】運算時,可能發(fā)生棧的上溢；在進行【2】運算時，可能發(fā)生棧的下溢。題目答案：進棧入?！砍鰲！?4. (1)分  &

81、#160;  題目ID號：11221     題目難度：容易    向棧中壓入元素的操作是【1】。題目答案：Push_stack】15. (1)分     題目ID號：11222     題目難度：容易    對棧進行退錢的操作是【1】題目答案：Pop_Stack】16. (2)分    

82、 題目ID號：11223     題目難度：容易    在一個循環(huán)隊列中，隊首指針指向【1】，隊尾指針指向【2】。題目答案：隊首元素】隊尾元素的下一個位置】17. (1)分     題目ID號：11224     題目難度：容易    從循環(huán)隊列中刪除個元素時，其操作是【1】。題目答案：DeQueue】18. (1)分 

83、0;   題目ID號：11225     題目難度：容易    在棧頂指針為s的鏈棧中，判定?？盏臈l件是【1】題目答案：s=NULL】19. (3)分     題目ID號：11226     題目難度：容易    棧和隊列是兩種特殊的線性表，棧的特點是【1】，隊列的特點是【2】。二者共同特點是只能在它們的【3】處添加和刪除結點。

84、題目答案：后進先出LIFOFILO】先進先出FIFO】端點】20. (2)分     題目ID號：11658     題目難度：容易    棧是【1】的線性表，其運算遵循【2】的原則。題目答案：操作受限限定僅在表尾進行插入和刪除操作】后進先出LIFO先進后出FILO】21. (2)分     題目ID號：11659     題目難度：容易

85、    設有一個空棧，棧頂指針為1000H(十六進制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是【1】，而棧頂指針值是【2】H。設棧為順序棧，每個元素占4個字節(jié)。題目答案：23】100CH】題目分析：PUSH為入棧操作，POP為出棧操作。根據(jù)棧的性質(zhì)，經(jīng)過PUSH,PUSH,POP運算之后，棧中存在元素1，輸出數(shù)據(jù)為2，然后經(jīng)過PUSH,POP，3入棧，3出棧，然后經(jīng)過PUSH,PUSH之后4，5入棧，此時出棧序列為2，3，棧中元素為1，4，5；每個元素占4個字節(jié)，所以棧頂指針

86、的值為1000H+3*4=100CH（十六進制數(shù)）22. (3)分     題目ID號：11660     題目難度：容易    已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是【1】;【2】;【3】；題目答案：newNode=new LinkNode(x)】newNode->link=r】r->link=newNode】題目分析：根據(jù)隊列的性質(zhì)，新插入的元素永遠插在隊尾。23. (1)分 &#

87、160;   題目ID號：11661     題目難度：容易    用下標0開始的N元數(shù)組實現(xiàn)循環(huán)隊列時，為實現(xiàn)下標變量M加1后在數(shù)組有效下標范圍內(nèi)循環(huán)，可采用的表達式是：M=【1】。題目答案：(M+1)%N】題目分析：循環(huán)隊列是解決假溢出的問題，通常把一維數(shù)組看成首尾相接。在循環(huán)意義下的加1運算通常用求模運算來實現(xiàn)。24. (3)分     題目ID號：11662    &#

88、160;題目難度：容易    當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack1.n表示，兩棧頂指針為top1與top2，則當棧1空時，top1為【1】，棧2空時，top2為【2】，棧滿時為【3】。題目答案：0】n+1】top1+1=top2】題目分析：為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一片連續(xù)的內(nèi)存空間時,應將兩棧的棧頂分別設在這片內(nèi)存空間的兩端,這樣,當兩個棧的棧頂在棧空間的某一位置相遇時，才產(chǎn)生上溢，即top1+1=top2。25. (5)分     題目ID號：11

89、663     題目難度：容易    在作進棧運算時應先判別棧是否【1】；在作退棧運算時應先判別棧是否       【2】；當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為【3】。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的空間時，應將兩棧的【4】分別設在內(nèi)存空間的兩端，這樣只有當【5】時才產(chǎn)生溢出。題目答案：滿】空】n】棧底】兩棧頂指針相鄰】26. (1)分  

90、0;  題目ID號：11664     題目難度：容易    無論對于順序存儲還是鏈式存儲的棧和隊列來說，進行插入和刪除運算的時間復雜度均相同為【1】。題目答案：O(1)】題目分析：對于棧用棧頂指針表示棧頂，而棧的插入和刪除操作均在棧頂進行。對于隊列用隊頭和隊尾指針分別表示允許插入和刪除的一端。27. (1)分     題目ID號：11665     題目難度：容易 

91、   在順序隊列中，當尾指針等于數(shù)組的上界，即使隊列不滿，再作入隊操作也會產(chǎn)生溢出，這種現(xiàn)象稱為【1】。題目答案：假溢出】題目分析：產(chǎn)生該現(xiàn)象的原因是，被刪元素空間在該元素被刪除后就永遠得不到使用。為了克服這種現(xiàn)象，采用循環(huán)隊列來實現(xiàn)。28. (6)分     題目ID號：11682     題目難度：容易     寫出下列中綴表達式的后綴形式：    【1】

92、0;A * B * C    【2】 - A + B - C + D    【3】 A* - B + C    【4】 (A + B) * D + E / (F + A * D)&

93、#160;+ C    【5】 A && B| ! (E > F)        注：按C+的優(yōu)先級)    【6】 !(A && !( (B < C)|(C > D) ) )|(C <

94、0;E)題目答案：AB*C*】A-B+C-D+】AB-*C+】AB+D*EFAD*+/C+】AB&&EF>!|】ABC<CD>|!&&!CE<|】五、問答1. (2)分     題目ID號：10781     題目難度：容易     設棧S的初始狀態(tài)為空，隊列Q的初始狀態(tài)為：    對棧S和隊列Q進行以下操作：   

95、60;Q中元素依次出隊，并壓入棧S中，直至Q為空；    依次彈出S中的元素并進入Q，直至S為空。    請畫出在上述操作后隊列Q的狀態(tài)。題目答案：2. (3)分     題目ID號：10783     題目難度：容易    設用一維數(shù)組Am存儲循環(huán)隊列，只設置一個隊頭指示器front和一個用以記錄隊列中元素個數(shù)的計數(shù)器count。在此情況下，隊空、隊滿的條件是什么?

96、如何確定將要入隊元素的位置?題目答案：隊空條件為count0；隊滿條件為countm；將要入隊元素的位置是(front+count)m3. (3)分     題目ID號：11144     題目難度：較易    在以順序方式存儲隊列時，會出現(xiàn)“假溢出”現(xiàn)象，請解釋這一現(xiàn)象，并說明解決“假溢出”的方法及其原理。題目答案：4. (2)分     題目ID號：11679  

97、   題目難度：容易    改寫順序棧的進棧成員函數(shù)Push (x )，要求當棧滿時執(zhí)行一個stackFull ( )操作進行棧滿處理。其功能是：動態(tài)創(chuàng)建一個比原來的棧數(shù)組大二倍的新數(shù)組，代替原來的棧數(shù)組，原來棧數(shù)組中的元素占據(jù)新數(shù)組的前MaxSize位置。題目答案：【解答】  template<class Type>void stack<Type> : push ( const&#

98、160;Type & item )     if ( isFull ( ) ) stackFull ( ); /棧滿，做溢出處理    elements  +top  = item; /進棧    template<class Type> void stack

99、<Type> : stackFull ( )     Type * temp = new Type  2 * maxSize  /創(chuàng)建體積大一倍的數(shù)組    for ( int i = 0; i <= top; i+ )  /傳送原數(shù)組的數(shù)據(jù)

100、      tempi = elementsi;    delete   elements;  /刪去原數(shù)組    maxSize *= 2;   /數(shù)組最大體積增長一倍    elements = temp; /新數(shù)組成為棧的數(shù)組空間  5. (4)分 &#

101、160;   題目ID號：11680     題目難度：容易      鐵路進行列車調(diào)度時, 常把站臺設計成棧式結構的站臺，如圖所示。試問：    (1) 設有編號為1,2,3,4,5,6的六輛列車, 順序開入棧式結構的站臺, 則可能的出棧序列有多少種?    (2) 若進站的六輛列車順序如上所述, 那么是否能夠得到435612

102、, 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出"進棧"或"出棧"的序列)。題目答案：6. (3)分     題目ID號：11681     題目難度：容易    試證明：若借助?？捎奢斎胄蛄?, 2, 3, , n得到一個輸出序列p1,

103、 p2, p3, , pn (它是輸入序列的某一種排列)，則在輸出序列中不可能出現(xiàn)以下情況，即存在i < j < k，使得pj < pk < pi。(提示：用反證法)題目答案：7. (3)分     題目ID號：11683     題目難度：容易    設表達式的中綴表示為a *

104、60;x - b / x2，試利用棧將它改為后綴表示ax * bx2/ -。寫出轉(zhuǎn)換過程中棧的變化。題目答案：8. (3)分     題目ID號：11684     題目難度：容易    已知An為整數(shù)數(shù)組，試寫出實現(xiàn)下列運算的遞歸算法：        (1) 求數(shù)組A中的最大整數(shù)。

105、60;       (2) 求n個整數(shù)的和。        (3) 求n個整數(shù)的平均值。題目答案：見ftp殷人昆-部分作業(yè)答案  5-19. (4)分     題目ID號：11685     題目難度：容易     已知Ackerman函數(shù)定義如下： 

106、;       (1) 根據(jù)定義，寫出它的遞歸求解算法；        (2) 利用棧，寫出它的非遞歸求解算法。題目答案：見ftp 殷人昆-部分作業(yè)答案  5-210. (1)分     題目ID號：11686     題目難度：容易     【背包

107、問題】設有一個背包可以放入的物品的重量為s，現(xiàn)有n件物品，重量分別為w1, w2, , wn。問能否從這n件物品中選擇若干件放入此背包中，使得放入的重量之和正好為s。如果存在一種符合上述要求的選擇，則稱此背包問題有解(或稱其解為真)；否則稱此背包問題無解(或稱其解為假)。試用遞歸方法設計求解背包問題的算法。（提示：此背包問題的遞歸定義如上：）題目答案：11. (4)分     題目ID號：11687     題目難度：容易   

108、; 【八皇后問題】設在初始狀態(tài)下在國際象棋棋盤上沒有任何棋子(皇后)。然后順序在第1行，第2行，。第8行上布放棋子。在每一行中有8個可選擇位置，但在任一時刻，棋盤的合法布局都必須滿足3個限制條件，即任何兩個棋子不得放在棋盤上的同一行、或者同一列、或者同一斜線上。試編寫一個遞歸算法，求解并輸出此問題的所有合法布局。(提示：用回溯法。在第n行第j列安放一個棋子時，需要記錄在行方向、列方向、正斜線方向、反斜線方向的安放狀態(tài)，若當前布局合法，可向下一行遞歸求解，否則可移走這個棋子，恢復安放該棋子前的狀態(tài)，試探本行的第j+1列。)題目答案：此為典型的回溯法問題。  在解決8

109、皇后時，采用回溯法。在安放第 i 行皇后時，需要在列的方向從 1 到 n 試探( j = 1, , n )：首先在第 j 列安放一個皇后，如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第 j 列安放的皇后。如果沒有出現(xiàn)攻擊，在第 j 列安放的皇后不動，遞歸安放第 i+1行皇后。    解題時設置 4 個數(shù)組：  

110、 col n ：coli 標識第 i 列是否安放了皇后   md2n-1 ：mdk 標識第 k 條主對角線是否安放了皇后   sd2n-1 ：sdk 標識第 k 條次對角線是否安放了皇后   qn ：qi 記錄第 i 行皇后在第幾列    利用行號i和列號j計算主對角線編號k的方法是k = n+i-j-1；計算次對角線編號k的方法是k = i+j。n皇后問題解法如下：  void Queen( int i )     for ( int j = 0; &#