數(shù)據(jù)結(jié)構(gòu)練習(xí)（含答案）：第三章棧和隊列

1、第三章 棧和隊列一、選擇題1. 一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（ ）。（A） edcba（B）decba（C）dceab （D）abcde 參考答案：C2.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（ ）。（A） 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)（B）散列方式和索引方式（C）鏈表存儲結(jié)構(gòu)和數(shù)組 （D）線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)參考答案：A3.判定一個棧ST(最多元素為m0)為空的條件是（ ）。（A） ST-top!=0 （B）ST-top=0 （C）ST-top!=m0 （D）ST-top=m0參考答案：B4.判定一個棧ST(最多元素為m0)為棧滿的條件是（ ）。（A）ST-t

2、op!=0 （B）ST-top=0 （C）ST-top!=m0-1（D）ST-top=m0參考答案：D5.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是（ ）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1參考答案：B6.循環(huán)隊列用數(shù)組A0,m-1存放其元素值,已知其頭尾指針分別是front和rear則當(dāng)前隊列中的元素個數(shù)是（ ）（A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front參考答案：B7.棧和隊列的共同點是（ ）（A） 都是先進(jìn)后出 （B）都是先進(jìn)先出（C）只允許在端

3、點處插入和刪除元素（D）沒有共同點參考答案：C8.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）。（A）abcd*+-（B）abc+*d- （C）abc*+d-（D）-+*abcd參考答案：B9.4個元素a1，a2，a3和a4依次通過一個棧，在a4進(jìn)棧前，棧的狀態(tài)，則不可能的出棧序是（）(A)a4，a3，a2，a1(B)a3，a2，a4，a1 (C)a3，a1，a4，a2(D)a3，a4，a2，a1參考答案：C10.以數(shù)組Q0.m1存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當(dāng)前隊列中元素的個數(shù)，隊列第一個元素的實際位置是（） (A)rearqulen(B

4、)rearqulenm(C)mqulen (D)1（rearmqulen）% m參考答案：D二、填空題1、1.棧的特點是_,隊列的特點是_。先進(jìn)后出; 先進(jìn)先出；2.線性表、棧和隊列都是_結(jié)構(gòu),可以在線性表的_位置插入和刪除元素，對于棧只能在_插入和刪除元素，對于隊列只能在_插入元素和_刪除元素。線性 ； 任何 ；棧頂；隊尾；對頭3.一個棧的輸入序列是12345,則棧有輸出序列12345是_。(正確/錯誤) 正確的4.設(shè)棧S和隊列Q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個棧，一個元素出棧后即進(jìn)入隊列Q，若6個元素出隊列的順序是a3，a5，a4，a6，a2，a1則棧S

5、至少應(yīng)該容納_個元素。4三、算法設(shè)計題 1.假設(shè)有兩個棧s1和s2共享一個數(shù)組stackM,其中一個棧底設(shè)在stack0處，另一個棧底設(shè)在stackM-1處。試編寫對任一棧作進(jìn)棧和出棧運(yùn)算的C函數(shù)push（x,i)和pop(i),i=l,2。其中i=1表示左邊的棧，,i=2表示右邊的棧。要求在整個數(shù)組元素都被占用時才產(chǎn)生溢出。#define M 100elemtype stackM;int top1=0,top2=m-1;int push(elemtype x,int i)if(top1-top2=1) return(1); /*上溢處理*/elseif(i=1) stacktop1+=x;i

6、f(i=2)stacktop2-=x;return(0); int pop(elemtype *px,int i)if(i=1)if(top1=0) return(1);else top1-;*px=stacktop1;return(0);elseif(i=2)if(top2=M-1) return(1);elsetop2+;*px=stacktop2;return(0); 2.利用兩個棧s1,s2模擬一個隊列時,如何用棧的運(yùn)算來實現(xiàn)該隊列的運(yùn)算?寫出模擬隊列的插入和刪除的C函數(shù)。 一個棧s1用于插入元素,另一個棧s2用于刪除元素.elemtype s1MAXSIZE,s2MAZSIZE;int top1,top2;void enqueue(elemtype x) if(top1=MAXSIZE) return(1); else push(s1,x); return(0); void dequeue(elemtype *px) elemtype x;