數(shù)據(jù)結(jié)構(gòu)-第3章棧和隊列自測卷答案

數(shù)據(jù)結(jié)構(gòu)-第3章棧和隊列自測卷答案第3章 棧和隊列 自測卷答案 姓名 班級題 一 二 三 四 五 六 總分號題 15 10 20 20 20 15 100分得分一、填空題（每空 1分，共15分）1.向量、棧和隊列都是 線性 結(jié)構(gòu)，可以在向量的任何 位置插入和刪除元素；對于棧只能在 棧頂插入和刪除元素；對于隊列只能在 隊尾 插入和隊首 刪除元素。棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為棧底 。3. 隊列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。在一個循環(huán)隊列中，隊首指針指向隊首元素的前一個位置。5.在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元素。6.向棧中壓入元素的操作是先 移動棧頂指針 ，后存入元素 。27.從循環(huán)隊列中刪除一個元素時，其操作是 先 移動隊首指針 ，后 取出元素 。8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長度等于 0 。解： he L=head 頭結(jié)點(diǎn) R=head二、判斷正誤（判斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）（×）1.線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型。錯，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲或鏈?zhǔn)酱鎯Γc元素數(shù)據(jù)類型無關(guān)。（×）2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊列不太常用。錯，不一定吧？調(diào)用子程序或函數(shù)常用， CPU中也用隊列。（√）3.棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（√）4.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實(shí)是特殊的線性表，對運(yùn)算的定義略有不同而已。（× ）5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。（ × ）6.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實(shí)是特殊的線性表，對運(yùn)算的定義略有不同而已。（ √ ）7.棧和隊列的存儲方式既可是順序方式，3也可是鏈接方式?！蹋?.兩個棧共享一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。×）9.隊是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯，后半句不對?！粒?0.一個棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯，有可能。三、單項選擇題 （每小題1分，共20分）B）1.棧中元素的進(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ù)棧的原理， n4必定是最后入棧的（事實(shí)上題目已經(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=m0A）4.判定一個隊列QU（最多元素為m0）為滿隊列的條件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1解：隊滿條件是元素個數(shù)為m0。由于約定滿隊時隊首指針與隊尾指針相差1，所以不必再減1了，應(yīng)當(dāng)選A。當(dāng)然，更正確的答案應(yīng)該取模，即： QU->front ==(QU->rear+1)%m0（ D ）5．?dāng)?shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，5ｆ為當(dāng)前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素的公式為（Ａ）r－f; （Ｂ）（n＋f－r）%n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）%n6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素a1、a2、a3和a4，對他們分別進(jìn)行棧操作或隊操作。在進(jìn)?；蜻M(jìn)隊操作時，按a1、a2、a3、a4次序每次進(jìn)入一個元素。假設(shè)?；蜿牭某跏紶顟B(tài)都是空。現(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次， 出棧一次，再進(jìn)棧兩次，出棧一次；這時，第一次出棧得到的元素是A，第二次出棧得到的元素是B是；類似地，考慮對這四個數(shù)據(jù)元素進(jìn)行的隊操作是進(jìn)隊兩次，出隊一次，再進(jìn)隊兩次，出隊一次；這時，第一次出隊得到的元素是C，第二次出隊得到的元素是D。經(jīng)操作后，最后在棧中或隊中的元素還有E個。供選擇的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：ABCDE＝2,4,1,2,267. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是A。設(shè)用一維數(shù)組A[1,?,n]來表示一個棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入（PUSH）一個新元素時，變量T的值B；從棧中彈出（POP）一個元素時，變量T的值C。設(shè)棧空時，有輸入序列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ī)進(jìn)出B，C：①加1②減1③不變④清0⑤加2⑥減2D：①a,b②b,c③c,a④b,a⑤c,b⑥a,cE：①n+1②n+2③n④n-1⑤n-2答案：ABCDE=2,2,1,6,4注意，向地址的高端生長， 稱為向上生成堆棧； 向地址低端生長叫向下生成堆棧， 本題中底部為 n，向地址的低端遞減生成，稱為向下生成堆棧。8. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？7內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時，應(yīng)先判別棧是否B。當(dāng)棧中元素為n個，做進(jìn)棧運(yùn)算時發(fā)生上溢，則說明該棧的最大容量為。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的D分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng)E時，才產(chǎn)生上溢。供選擇的答案：A，B：①空②滿③上溢④下溢C：①n-1②n③n+1④n/2D：①長度②深度③棧頂④棧底E：①兩個棧的棧頂同時到達(dá)?？臻g的中心點(diǎn) ②其中一個棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)③兩個棧的棧頂在達(dá)?？臻g的某一位置相遇④兩個棧均不空，且一個棧的棧頂?shù)竭_(dá)另一個棧的棧底答案：ABCDE＝2, 1, 2, 4, 3四、簡答題（每小題 4分，共20分）81.說明線性表、棧與隊的異同點(diǎn)。劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表 LIFO；隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表 FIFO。②用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場，隊列用于 多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2.設(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,13,2,4,13,2,1,4③進(jìn)2個之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進(jìn)1個之后再出的情況，有5種，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,33.假設(shè)正讀和反讀都相同的字符序列為“回文” ，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計算機(jī)，請分析用線性表、堆棧和隊列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲，可以實(shí)現(xiàn)，靠循環(huán)變量（j--）從表尾開始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動作實(shí)9現(xiàn)。（但堆棧是先減后壓還是??）若正文是單鏈表形式存儲，則等同于隊列，需開輔助空間，可以從鏈?zhǔn)组_始入棧，全部壓入后再依次輸出。4.順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界， 不能再有入隊操作， 但其實(shí)數(shù)組中還有空位置， 這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決隊滿隊空的辦法有三：① 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；② 浪費(fèi)一個元素的空間，用于區(qū)別隊滿還是隊空。③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度） 。我們常采用法②，即隊頭指針、隊尾指針中有一個指向?qū)嵲兀硪粋€指向空閑元素。判斷循環(huán)隊列隊空標(biāo)志是： f=rear 隊滿標(biāo)志是：f=(r+1)%N5.設(shè)循環(huán)隊列的容量為40（序號從0到39），現(xiàn)經(jīng)過一系列的入隊和出隊運(yùn)算后，有front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環(huán)隊列中各有元素多少個？答：用隊列長度計算公式： (N＋r－f)%N①L=（40＋19－11）%40=8 ②L=（40＋11－19）%40=32五、閱讀理解（每小題5分，共20分。至少要寫出思路）按照四則運(yùn)算加、減、乘、除和冪運(yùn)算（↑）優(yōu)先關(guān)10系的慣例，并仿照教材例3-2的格式，畫出對下列算術(shù)表達(dá)式求值時操作數(shù)棧和運(yùn)算符棧的變化過程：A－B×C/D+E↑F答：2.寫出下列程序段的輸出結(jié)果（棧的元素類型 SElemType為char）。voidmain(){StackS;Charx,y;InitStack(S);11X=’c’;y=’k’;Push(S,x);Push(S, ’Push(S,y);a’Pop(S,x);Push(S, );Push(S,x);’t’Pop(S,x);Push(S, ’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};Printf(x);}答：輸出為“stack”。寫出下列程序段的輸出結(jié)果（隊列中的元素類型QElemType為char）。voidmain(){QueueQ; InitQueue(Q);Charx=’e’;y=’c’;EnQueue(Q,’h’);QueueEn(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.簡述以下算法的功能（棧和隊列的元素類型均為 int）。12voidalgo3(Queue&Q){StackS;intd;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分。至少要寫出思路）假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量（可理解為每個字符占用一個數(shù)組元素），表示被判別的表達(dá)式，tag為布爾型變量。答：用堆棧st進(jìn)行判定，將(、[或{入棧，當(dāng)遇到}、]或)時，檢查當(dāng)前棧頂元素是否是對應(yīng)的13(、[或{，若是則退棧，否則返回表示不配對。當(dāng)整個算術(shù)表達(dá)式檢查完畢時，若棧為空表示括號正確配對，否則不配對。編程后的整個函數(shù)如下（李書 P31—32）#definem0100 /*m0為算術(shù)表達(dá)式中最多字符個數(shù)*/correct(exp,tag)charexp[m0];inttag;{charst[m0];inttop=0,i=1;tag=1;while(i<=m0&&tag){if(exp[i]== ‘(‘||exp[i]== ’）[‘||exp[i]=/*遇到=‘、(‘’或[‘’，{‘則將其入棧*/{top++;st[top]=exp[i];}if(exp[i]== ’/*)’遇到)’)，’若棧頂是‘，(‘則繼續(xù)處理，否則以不配對返回 */if(st[top]== )top‘(--‘;elsetag=0;if(exp[i]== ’)/*’遇到)’]，’若棧頂是‘，[‘則繼續(xù)14處理，否則以不配對返回 */if(st[top]== ]‘top[--‘;elsetag=0;if(exp[i]== ’/*)’遇到)’}，’若棧頂是‘，{‘則繼續(xù)處理，否則以不配對返回 */if(st[top]== ‘--{;‘topelsetag=0;i++;}if(top>0)tag=0; /*若棧不空，則不配對*/}對應(yīng)答案：3.19StatusAllBrackets_Test(char *str)//判別表達(dá)式中三種括號是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){15if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')returnERROR;if(*p=='}'&&c!='{')returnERROR;//必須與當(dāng)前棧頂括號匹配}}//forif(!StackEmpty(s))returnERROR;returnOK;}//AllBrackets_Test答案（已上機(jī)通過）#include<stdio.h>#include<stdlib.h>voidpush(charx);voidpop();voidcorrect(enumBoolean&tag);//原來的定義是voidcorrect(structStack*head,enumBoolean&tag);typedefstructStack16{chardata;structStack*next;};structStack*head,*p;enumBoolean{FALSE,TRUE}tag;voidmain(){head=(structStack*)malloc(sizeof(structStack));head->data='S';head->next=NULL;head'sdatahasnotbeeninitialized!!correct(tag);if(tag)printf("Right!");elseprintf("Wrong!");}voidpush(charx)17{p=(structStack*)malloc(sizeof(structStack));if(!p)printf("There'snospace.\n");else{p->data=x;p->next=head;head=p;}}//ifyoudefinethe"Correct"functionlikethat//DebugwillshowthatthePushactiondoesn’takeeffectionvoidpop(){if(head->next==NULL)printf("Thestackisempty.\n");else{p=head;18head=head->next;free(p);}}//voidcorrect(structStack*head,enumBoolean&tag)voidcorrect(enumBoolean&tag){inti;chary;printf("Pleaseenterabds:");for(i=0;y!='\n';i++){scanf("%c",&y);if((y==')'&&head->data=='(')||(y==']'&&head->data=='[')||(y=='}'&&head->data=='{'))pop();elseif((y=='(')||(y=='[')||(y=='{