幫你掌握數(shù)據(jù)結(jié)構(gòu)(第三章系列經(jīng)典試題及答案)

1、第3章 棧和隊列 一、填空題（每空1分，共15分）1. 向量、棧和隊列都是 線性 結(jié)構(gòu)，可以在向量的 任何 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 。不允許插入和刪除運算的一端稱為 棧底 。3. 隊列 是被限定為只能在表的一端進(jìn)行插入運算，在表的另一端進(jìn)行刪除運算的線性表。4. 在一個循環(huán)隊列中，隊首指針指向隊首元素的 前一個 位置。5. 在具有n個單元的循環(huán)隊列中，隊滿時共有 n-1 個元素。6. 向棧中壓入元素的操作是先 存入元素 ，后 移動棧頂指針。7. 從循環(huán)隊

2、列中刪除一個元素時，其操作是 先 移動隊首指針 ，后 取出元素 。8. 00年統(tǒng)考題帶表頭結(jié)點的空循環(huán)雙向鏈表的長度等于 0 。head解： 二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）（ × ）1. 線性表的每個結(jié)點只能是一個簡單類型，而鏈表的每個結(jié)點可以是一個復(fù)雜類型。 錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈?zhǔn)酱鎯?，與元素數(shù)據(jù)類型無關(guān)。（ × ）2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。 錯，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊列。（ ）3. 棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先

3、出型結(jié)構(gòu)。（ ）4. 對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。 正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（ × ）5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。（ × ）6. 棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（ ）7. 棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。 （ ）8. 兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把兩個棧的棧底

4、分別設(shè)在這片內(nèi)存空間的兩端。 （ × ）9. 隊是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯，后半句不對。（ × ）10. 一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。 錯，有可能。三、單項選擇題（每小題1分，共20分）（ B ）1. 00年元月統(tǒng)考題棧中元素的進(jìn)出原則是先進(jìn)先出 后進(jìn)先出 棧空則進(jìn) 棧滿則出（ C ）2. 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為i n=i n-i+1 不確定解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的（事實上題目

5、已經(jīng)表明了），那么輸入順序必定是1，2，3，n，則出棧的序列是n，3，2，1。（若不要求順序出棧，則輸出序列不確定）（ B ）3. 判定一個棧ST（最多元素為m0）為空的條件是ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0（ A ）4. 判定一個隊列QU（最多元素為m0）為滿隊列的條件是QU->rear-QU->front = = m0 QU->rear QU->front 1= = m0 QU->front = = QU->rear QU->front = = Q

6、U->rear+1解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以不必再減1了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即：QU->front = = (QU->rear+1% m0（ D ）5數(shù)組用來表示一個循環(huán)隊列，為當(dāng)前隊列頭元素的前一位置，為隊尾元素的位置，假定隊列中元素的個數(shù)小于，計算隊列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n6. 【98初程P71】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素a1、a2、a3和a4，對他們分別進(jìn)行棧操

7、作或隊操作。在進(jìn)?；蜻M(jìn)隊操作時，按a1、a2、a3、a4次序每次進(jìn)入一個元素。假設(shè)?；蜿牭某跏紶顟B(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類似地，考慮對這四個數(shù)據(jù)元素進(jìn)行的隊操作是進(jìn)隊兩次，出隊一次，再進(jìn)隊兩次，出隊一次；這時，第一次出隊得到的元素是 C ，第二次出隊得到的元素是 D 。經(jīng)操作后，最后在棧中或隊中的元素還有 E 個。供選擇的答案：AD：a1 a2 a3 a4E： 1 2 3 0答：ABCDE2, 4, 1, 2, 27. 【94初程P75】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？

8、內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。棧是一種線性表，它的特點是 A 。設(shè)用一維數(shù)組A1,n來表示一個棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值 B ；從棧中彈出（POP）一個元素時，變量T的值 C 。設(shè)?？諘r，有輸入序列a，b，c，經(jīng)過PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機進(jìn)出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,a b,a c,b a,cE： n+1 n+

9、2 n n-1 n-2答案：ABCDE=2, 2, 1, 6, 4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成堆棧，本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8. 【91初程P77】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進(jìn)棧運算時，應(yīng)先判別棧是否 A ；在做退棧運算時，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個，做進(jìn)棧運算時發(fā)生上溢，則說明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時，

10、才產(chǎn)生上溢。供選擇的答案：A，B：空 滿 上溢 下溢C： n-1 n n+1 n/2D： 長度 深度 棧頂 棧底E：兩個棧的棧頂同時到達(dá)?？臻g的中心點 其中一個棧的棧頂?shù)竭_(dá)棧空間的中心點 兩個棧的棧頂在達(dá)棧空間的某一位置相遇 兩個棧均不空，且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底答案：ABCDE2, 1, 2, 4, 3四、簡答題（每小題4分，共20分）1. 【嚴(yán)題集3.2和3.11】說明線性表、棧與隊的異同點。答：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：運算規(guī)則不同，線性表為隨機存取，而棧

11、是只允許在一端進(jìn)行插入、刪除運算，因而是后進(jìn)先出表LIFO；隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。2. 【統(tǒng)考書P60 4-11，難于嚴(yán)題集3.1】設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的順序。答：至少有14種。 全進(jìn)之后再出情況，只有1種：4,3,2,1 進(jìn)3個之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4

12、2,1,4,3 2, 3,1,4 進(jìn)1個之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33. 【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab則不是回文。假設(shè)一字符序列已存入計算機，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機存儲，可以實現(xiàn)，靠循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進(jìn)先出，不易實現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，

13、或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。4. 【統(tǒng)考書P60 4-13】順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：1 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；2 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。3 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法，即隊頭指針、隊

14、尾指針中有一個指向?qū)嵲?，而另一個指向空閑元素。判斷循環(huán)隊列隊空標(biāo)志是： f=rear 隊滿標(biāo)志是：f=(r+1%N5. 【統(tǒng)考書P60 4-14】設(shè)循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運算后，有 front=11，rear=19; front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式： (Nrf% N L=（401911）% 40=8 L=（401119）% 40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）1. 【嚴(yán)題集3.7】按照四則運算加、減、乘、除和冪運算（）優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格

15、式，畫出對下列算術(shù)表達(dá)式求值時操作數(shù)棧和運算符棧的變化過程：AB×C/D+EF答：2. 【嚴(yán)題集3.3】寫出下列程序段的輸出結(jié)果（棧的元素類型SElem Type為char）。void main( Stack S;Char x,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;答：輸出為“stack”。3. 【嚴(yán)題集3.12】寫出下列程序段的輸出結(jié)

16、果（隊列中的元素類型QElem Type為char）。void main( Queue Q; Init Queue (Q;Char x=e; y=c;EnQueue (Q,h; EnQueue (Q,r; EnQueue (Q, y;DeQueue (Q,x; EnQueue (Q,x; DeQueue (Q,x; EnQueue (Q,a; while(!QueueEmpty(Q DeQueue (Q,y;printf(y; ;Printf(x;答：輸出為“char”。4. 【嚴(yán)題集3.13】簡述以下算法的功能（棧和隊列的元素類型均為int）。void algo3(Queue &QS

17、tack S; int d;InitStack(S;while(!QueueEmpty(Q DeQueue (Q,d; Push(S,d;while(!StackEmpty(S Pop(S,d; EnQueue (Q,d; 答：該算法的功能是：利用堆棧做輔助，將隊列中的數(shù)據(jù)元素進(jìn)行逆置。六、算法設(shè)計（每小題5分，共15分。至少要寫出思路）1. 【李春葆及嚴(yán)題集3.19】假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù)correct(exp,tag；其中：exp為字符串類型的變量（可理解為每個字符占用一個數(shù)組元素），表示被判別的表達(dá)式，ta

18、g為布爾型變量。答：用堆棧st進(jìn)行判定，將 ( 、 或 入棧，當(dāng)遇到 、 或 時，檢查當(dāng)前棧頂元素是否是對應(yīng)的( 、 或 ，若是則退棧，否則返回表示不配對。當(dāng)整個算術(shù)表達(dá)式檢查完畢時，若棧為空表示括號正確配對，否則不配對。編程后的整個函數(shù)如下（李書P3132）#define m0 100 /*m0為算術(shù)表達(dá)式中最多字符個數(shù)*/correct(exp,tagchar expm0;int tag;char stm0;int top=0, i=1;tag=1;while (i<=m0 && tagif (expi= = (|expi= =|expi= =） /*遇到(、或，則將

19、其入棧*/top+;sttop=expi;if (expi= = /*遇到 ，若棧頂是(，則繼續(xù)處理，否則以不配對返回*/if(sttop= =( top-;else tag=0;if (expi= = /*遇到 ，若棧頂是，則繼續(xù)處理，否則以不配對返回*/if(sttop= = top-;else tag=0;if (expi= = /*遇到 ，若棧頂是，則繼續(xù)處理，否則以不配對返回*/if(sttop= = top-;else tag=0;i+;if(top>0tag=0; /*若棧不空，則不配對*/嚴(yán)題集對應(yīng)答案：3.19 Status AllBrackets_Test(char

20、*str/判別表達(dá)式中三種括號是否匹配 InitStack(s; for(p=str;*p;p+ if(*p='('|*p=''|*p='' push(s,*p; else if(*p=''|*p=''|*p='' if(StackEmpty(s return ERROR; pop(s,c; if(*p=''&&c!='(' return ERROR; if(*p=''&&c!='' return ERR

21、OR; if(*p=''&&c!='' return ERROR; /必須與當(dāng)前棧頂括號匹配 /for if(!StackEmpty(s return ERROR; return OK; /AllBrackets_Test 2001級通信6班張沐同學(xué)答案（已上機通過）#include #include void push(char x;void pop(;void correct(enum Boolean &tag;/原來的定義是void correct(struct Stack* head,enum Boolean &tag;t

22、ypedef struct Stackchar data;struct Stack *next;struct Stack *head,*p;enum BooleanFALSE,TRUEtag;void main(head=(struct Stack*malloc(sizeof(struct Stack;head->data='S'head->next=NULL;/ head's data has not been initialized! correct(tag;if(tagprintf("Right!"elseprintf("

23、Wrong!"void push(char xp=(struct Stack*malloc(sizeof(struct Stack;if(!pprintf("There's no space.n"elsep->data=x;p->next=head;head=p;/ if you define the "Correct" function like that/Debug will show that the Push action doesnt take effectionvoid pop(if(head->next=

24、NULLprintf("The stack is empty.n"elsep=head;head=head->next;free(p;/void correct(struct Stack* head,enum Boolean &tagvoid correct(enum Boolean &tagint i;char y;printf("Please enter a bds:"for(i=0;y!='n'i+scanf("%c",&y;if(y=''&&head->data='('|(y=''&&head->data=''|(y=''&&head->data=''pop(;else if(y='('|(y=''|(y=''push(y;/*調(diào)試程序顯示，y并沒有被推入堆棧中。即head->data的值在Push中顯示為y的值，但是出Push函數(shù)。馬上變成Null。*/elsecontinue;if(head->nex