第3章棧和隊列答案[1]

1、第3章棧和隊列自測卷答案姓名班級題號二三四五總分題分151020202015100得分一、填空題（每空1分，共15分）1. 【李春葆】向量、棧和隊列都是線性 結(jié)構(gòu)，可以在向量的 任何位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入和 隊首 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂 。不允許插入和刪除運(yùn)算的一端稱為棧底 。3. 隊列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端 進(jìn)行刪除運(yùn)算的線性表。4. 在一個循環(huán)隊列中，隊首指針指向隊首元素的前一個 位置。5. 在具有n個單元的循環(huán)隊列中，隊滿時共有 n-1 個元素。6. 向

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

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

4、溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩 端。（X ） 9.隊是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一 種先進(jìn)后出型結(jié)構(gòu)。錯，后半句不對。（X ） 10. 一個棧的輸入序列是12345,則棧的輸岀序列不可能是 12345。錯，有可能。三、單項選擇題（每小題1分，共20分）（B ） 1.K00年元月統(tǒng)考題棧中元素的進(jìn)出原則是A.先進(jìn)先出B.后進(jìn)先出C.?？談t進(jìn)D.棧滿則出（C ） 2. K李春葆H若已知一個棧的入棧序列是1, 2, 3,，n,其 輸出序列為pl, p2, p3,，pn,若pl二n,則pi為A. iB. n=iC. n-i+1D.不確定解釋：當(dāng)pl二n,即n是

5、最先出棧的，根據(jù)棧的原理，n必定是最后入棧的 （事實上題目已經(jīng)表明了），那么輸入順序必定是1, 2, 3,，n,則出棧的序 列是n,，3, 2, lo（若不要求順序出棧，則輸出序列不確定）（B ） 3. K李春葆H判定一個棧ST （最多元素為mO）為空的條件是A. ST->top<>0B. ST-top二0C. ST->top<>mOD. ST->top=mO（A ） 4. K李春葆H判定一個隊列QU （最多元素為mO）為滿隊列的條 件是A. QU->rear QU>front = = mOB. QU->rear QU>fron

6、t 1= = mOC. QU->front 二二 QU->rearD. QU->front 二二 QU->rear+l解：隊滿條件是元素個數(shù)為mO。由于約定滿隊時隊首指針與隊尾指針相差1, 所以不必再減1 了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即：QU->front =（QU->rear+l）% mO(D ) 5.數(shù)組Q n用來表示一個循環(huán)隊列，f為當(dāng)前隊列頭元素 的詢一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n,計算隊列中元 素的公式為(A) r-f;( B )(n+f-r) % n; ( C ) n+rf;( D ) (n+r f) % n

7、6.【98初程P71】從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的 最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素al、邊、&3和必，對他們分別進(jìn)行棧操作或隊操作。在 進(jìn)?；蜻M(jìn)隊操作時，按&1、&、&3、M次序每次進(jìn)入一個元素。假設(shè)?；蜿牭某?始狀態(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)操作后，最

8、后在棧中或隊中的元素還 有 E 個。供選擇的答案：AD： ®al ®a2 a3 a4E： ®1230答：ABCDE = 2,4,1,2,27.【94初程P75從供選擇的答案中，選出應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。棧是一種線性表，它的特點是 A 。設(shè)用一維數(shù)組Al,n來表示一個 棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入 (PUSH) 一個新元素時，變量T的值 B ；從棧中彈出(POP) 一個元素時，變 量T的值 C 。設(shè)棧空時，有輸入序列a, b, c,經(jīng)過PUSH, POP, PUSH, PUSH, P

9、OP操作后，從棧中彈出的元素的序列是D ,變量T的值是 E 。供選擇的答案：A：先進(jìn)先出后進(jìn)先出進(jìn)優(yōu)于出出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B,C：加1減1不變清0 加2減2D：6 bb, cc, ab, ac, b a, cE：n+1n+2nnTn-2答案：ABCDE二2,2,1,6,4注意，向地址的高端生長，稱為向上生成堆棧；向地址低端生長叫向下生成 堆棧，本題中底部為n,向地址的低端遞減生成，稱為向下生成堆棧。8.【91初程P77】 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi) 的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時，應(yīng)先判別棧是 否 B 。當(dāng)棧

10、中元素為n個，做進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最大容量 為 C O為了增加內(nèi)存空間的利用率和減少溢出的可能性，山兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的 D分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時，才產(chǎn)生上溢。供選擇的答案:A, B：空上溢下溢C：(Dn-ln+1n/2D： 長度深度棧頂棧底E：兩個棧的棧頂同時到達(dá)棧空間的中心點其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點兩個棧的棧頂在達(dá)?？臻g的某一位置相遇 兩個棧均不空，且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底答案：ABCDE=2,1, 2,4,3四、簡答題（每小題4分，共20分）1. 【嚴(yán)題集3. 2和3. 11】說明線性表、棧與隊的異同點。于答

11、：相同點：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或 鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運(yùn) 算加以限制。不同點：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插 入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊列是只允許在一端進(jìn)行插入、另一端 進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFOo 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊列用于多道作業(yè)處理、指令 寄存及其他運(yùn)算等等。2. 【統(tǒng)考書P60 4-11,難于嚴(yán)題集3. 1®設(shè)有編號為1, 2, 3, 4的四輛 列車，順序進(jìn)入一個棧式結(jié)構(gòu)的車站，具體寫出這四輛列車開出車站的所有可能的 順序。

12、全進(jìn)之后再出悄況，只有1種：4, 3, 2, 1于答：至少有14種。3,4,2, 13,2,4, 13,2, 1,42, 4, 3, 12,3,4, 12, 1,1,4, 3, 21,3, 2, 41,3,4,21 進(jìn)3個之后再出的惜況，有3種, 進(jìn)2個之后再出的惜況，有5種,3,42, 1,4,32, 1,3,4 進(jìn)1個之后再出的情況，有5種,2, 3, 41, 2,4, 33. 【劉自編】假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，4 abba *和abcba'是回文，*abcde*和4 ababab *則不是回文。假設(shè)一字符 序列已存入訃算機(jī)，請分析用線性表、堆棧和隊列等方式

13、正確輸出其回文的可能 性？答：線性表是隨機(jī)存儲，可以實現(xiàn)，鼎循環(huán)變量（j-）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實現(xiàn)，靠正序入棧、逆序出棧即可;隊列是先進(jìn)先出，不易實現(xiàn)。哪種方式最好，要具體悄況具體分析。若正文在機(jī)內(nèi)已是順序存儲，則直接 用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實 現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始 入棧，全部壓入后再依次輸出。4. 【統(tǒng)考書P60 4-13順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán) 隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操

14、 作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：1設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；2浪費(fèi)一個元素的空間，用于區(qū)別隊滿還是隊空。3使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。我們常采用法，即隊頭指針、隊尾指針中有一個指向?qū)嵲?，而另一個指 向空閑元素。判斷循環(huán)隊列隊空標(biāo)志是：f=rear隊滿標(biāo)志是：f=（r+l）%N5. 【統(tǒng)考書P60 4-14設(shè)循環(huán)隊列的容量為40 （序號從0到39）,現(xiàn)經(jīng)過 一系列的入隊和岀隊運(yùn)算后，有front二19, rearll；問在這兩種情況下, front二11, rear=19;循環(huán)隊列中各有

15、元素多少個？答：用隊列長度計算公式：（N+r-f）% N L二（40+19-11） % 40=8 L二（40+11-19） %40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）1.【嚴(yán)題集3. 7】按照四則運(yùn)算加、減、乘、除和幕運(yùn)算（f ）優(yōu)先關(guān)系 的慣例，并仿照教材例3-2的格式，畫出對下列算術(shù)表達(dá)式求值時操作數(shù)棧和運(yùn)算 符棧的變化過程：A-BXC/D+E t F答:序號OPTRH當(dāng)n字n備注ABc./D+EAF-（炸）1tt呻 hQPNrVA1)2A2"T-pushCOPTR/-')3U 一ALPh(OPND/B>1U -ABpu*h()PTR/ *)5

16、# ABptth(OPND/C)6w - »ABC舊約令二BC7tt AT.pwhCOPTR/)8n AT,TSPND.m9«-/AT,D歸的令T,-T./D10Ah歸約令Tj-A-=11TipuiCOPTR/*)12TjpiuhCOi-NP/E )TaEpuiih(OPTR.* I )U科4 *TaEpuMhCOPND/D15TaEF歸約令TlE,P169十歸約令T,-T, + T.17nT>ret urn(K)2.【嚴(yán)題集3. 3】寫岀下列程序段的輸岀結(jié)果（棧的元素類型SElem Type為 char)void main( ) Stack S;Char x, y;

17、InitStack(S);Xi c，g L ;Push(S, x) ; Push(S, af ); 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 v o3. 【嚴(yán)題集3. 12】寫出下列程序段的輸出結(jié)果(隊列中的元素類型QElemType char)。void main( ) Queue Q; Init Queue (Q);Ch

18、ar x二'e ； y二'cEnQueue (Q, ' h)； EnQueue (Q, ')； 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” o4. 【嚴(yán)題集3. 13】簡述以下算法的功能(棧和隊列的元素類型均為int) ovoid algo3(Queue &Q)Stack S; int d;InitStack

19、(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分，共13分。至少要寫出思路）1.【李春葆及嚴(yán)題集3. 19】假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧 和花括弧三種類型的括弧，編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù) correct （exp, tag）；其中：exp為字符串類型的變量（可理解為每個字符占用一個 數(shù)組元素），表示被判別的表達(dá)式，tag為布爾型變

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

21、39;)/*遇到''或'則將其入棧*/top 卄;sttop二expi;if (expi=二')')/*遇到')'，若棧頂是'('，則繼續(xù)處理，否 則以不配對返回*/if (st top二二'(')top;else tdg=0;辻(expi二二')')/*遇到''，若棧頂是則繼續(xù)處理， 否則以不配對返回權(quán)if (st top = = '' top;else tag=0;if (expi二二')')/*遇到'',若棧頂是則繼續(xù)處理

22、，否 則以不配對返回*/if(sttop=二' ' top-;else tag=0;辻(top>0)tag=0;/*若棧不空，則不配對*/嚴(yán)題集對應(yīng)答案：3. 19Status AllBrackets_Test (char *str)/判別表達(dá)式中三種括號是否匹配InitStack(s);for(p二str;*p;p+)辻(*p二二( *p二二 *p二二，) push(s, *p);else if(*p二二')，*p二二'' *p二二'，)if(StackEmpty(s) return ERROR;pop(s, c);辻(*p二二'

23、)' &&c(') return ERROR;辻(*p二二''&&c!二'')return ERROR;if (*p='&&c!二'') return ERROR; /必須與當(dāng)前棧頂括號匹配/for辻(!StackEmpty(s) return ERROR;return OK;/AllBrackets_Test另一答案(已上機(jī)通過)#include<stdio. h>#include<stdlib. h>void push(char x);void p

24、op ();void correct(enum Boolean &tag);/原來的定 義是 void correct (struct Stack* head, enum Boolean &tag):typedef 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 (tag)printf("Right!");elseprintf("Wrong!");void push(char x)p= (struct Stack*)malloc(sizeof(struct Stack);辻(8)printf ("There's no spacerT);elsep->data=x;p->next=head;head