c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列自測(cè)卷答案

第3章棧和隊(duì)列自測(cè)卷答案姓名班級(jí)題號(hào)一二三四五六總分題分151020202015100得分一、填空題〔每空1分，共15分〕1.【李春葆】向量、棧和隊(duì)列都是線性構(gòu)造，可以在向量的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。3.隊(duì)列是被限定為只能在表的一端進(jìn)展插入運(yùn)算，在表的另一端進(jìn)展刪除運(yùn)算的線性表。4.在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元素。6.向棧中壓入元素的操作是先挪動(dòng)棧頂指針，后存入元素。7.從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先挪動(dòng)隊(duì)首指針，后取出元素。8.〖00年統(tǒng)考題〗帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于0。L=head頭結(jié)點(diǎn)RL=head頭結(jié)點(diǎn)R=headhead二、判斷正誤〔判斷以下概念的正確性，并作出簡(jiǎn)要的說(shuō)明?！场裁款}1分，共10分〕〔×〕1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò)，線性表是邏輯構(gòu)造概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)?！病痢?.在表構(gòu)造中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。〔√〕3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)展的線性表，是一種后進(jìn)先出型構(gòu)造?！病獭?.對(duì)于不同的使用者，一個(gè)表構(gòu)造既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯構(gòu)造，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。〔×〕5.棧和鏈表是兩種不同的數(shù)據(jù)構(gòu)造。錯(cuò)，棧是邏輯構(gòu)造的概念，是特殊殊線性表，而鏈表是存儲(chǔ)構(gòu)造概念，二者不是同類項(xiàng)?！病痢?.棧和隊(duì)列是一種非線性數(shù)據(jù)構(gòu)造。錯(cuò)，他們都是線性邏輯構(gòu)造，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已?！病獭?.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式?！病獭?.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為進(jìn)步內(nèi)存利用率，減少溢出時(shí)機(jī)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。〔×〕9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)展的線性表，是一種先進(jìn)后出型構(gòu)造。 錯(cuò)，后半句不對(duì)?！病痢?0.一個(gè)棧的輸入序列是12345，那么棧的輸出序列不可能是12345。錯(cuò)，有可能。三、單項(xiàng)選擇題〔每題1分，共20分〕〔B〕1.〖00年元月統(tǒng)考題〗棧中元素的進(jìn)出原那么是Ａ．先進(jìn)先出Ｂ．后進(jìn)先出Ｃ．?？漳敲催M(jìn)Ｄ．棧滿那么出〔C〕2.〖李春葆〗假設(shè)一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，假設(shè)p1=n，那么pi為Ａ．iＢ．n=iＣ．n-i+1Ｄ．不確定解釋：當(dāng)p1=n，即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的，那么輸入順序必定是1，2，3，…，n，那么出棧的序列是n，…，3，2，1?！睟〕3.〖李春葆〗斷定一個(gè)棧ST〔最多元素為m0〕為空的條件是Ａ．ST->top<>0Ｂ．ST->top=0Ｃ．ST->top<>m0Ｄ．ST->top=m0〔B〕4.〖李春葆〗斷定一個(gè)隊(duì)列QU〔最多元素為m0〕為滿隊(duì)列的條件是Ａ．QU->rear－QU->front==m0Ｂ．QU->rear－QU->front－1==m0Ｃ．QU->front==QU->rearＤ．QU->front==QU->rear+1〔D〕5．?dāng)?shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素的公式為〔Ａ〕r－f;〔Ｂ〕〔n＋f－r〕%n;〔Ｃ〕n＋r－f;〔Ｄ〕〔n＋r－f〕%n6.【98初程P71】從供選擇的答案中，選出應(yīng)填入下面表達(dá)？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4，對(duì)他們分別進(jìn)展棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空。現(xiàn)要進(jìn)展的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是A，第二次出棧得到的元素是B是；類似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)展的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是C，第二次出隊(duì)得到的元素是D。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有E個(gè)。供選擇的答案：A～D：①a1②a2③a3④a4E：①1②2③3④0答：ABCDE＝2,4,1,2,27.【94初程P75】從供選擇的答案中，選出應(yīng)填入下面表達(dá)？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是A。設(shè)用一維數(shù)組A[1,…,n]來(lái)表示一個(gè)棧，A[n]為棧底，用整型變量T指示當(dāng)前棧頂位置，A[T]為棧頂元素。往棧中推入〔PUSH〕一個(gè)新元素時(shí)，變量T的值B；從棧中彈出〔POP〕一個(gè)元素時(shí)，變量T的值C。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過(guò)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注意，向地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，此題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8.【91初程P77】從供選擇的答案中，選出應(yīng)填入下面表達(dá)？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否A；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否B。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，那么說(shuō)明該棧的最大容量為C。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的D分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng)E時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B：①空②滿③上溢④下溢C： ①n-1②n③n+1④n/2D：①長(zhǎng)度②深度③棧頂④棧底E：①兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn)②其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)③兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇④兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE＝2,1,2,4,3四、簡(jiǎn)答題〔每題4分，共20分〕1.【嚴(yán)題集3.2①和3.11①】說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。劉答：一樣點(diǎn)：都是線性構(gòu)造，都是邏輯構(gòu)造的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：①運(yùn)算規(guī)那么不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)展插入、刪除運(yùn)算，因此是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)展插入、另一端進(jìn)展刪除運(yùn)算，因此是先進(jìn)先出表FIFO。②用處不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令存放及其他運(yùn)算等等。2.【統(tǒng)考書P604-11，難于嚴(yán)題集3.1①】設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式構(gòu)造的車站，詳細(xì)寫出這四輛列車開出車站的所有可能的順序。劉答：至少有14種。①全進(jìn)之后再出情況，只有1種：4，3，2，1②進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,13,2,4,13,2,1,4③進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,12,3,4,12,1,3,42,1,4,32,1,3,4④進(jìn)1個(gè)之后再出的情況，有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ī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量〔j--〕從表尾開場(chǎng)打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要詳細(xì)情況詳細(xì)分析。假設(shè)正文在機(jī)內(nèi)已是順序存儲(chǔ)，那么直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)?！驳褩Ｊ窍葴p后壓還是……〕假設(shè)正文是單鏈表形式存儲(chǔ)，那么等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_場(chǎng)入棧，全部壓入后再依次輸出。4.【統(tǒng)考書P604-13】順序隊(duì)的“假溢出〞是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出〞。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的方法有三：設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)〔即隊(duì)列長(zhǎng)度〕。我們常采用法②，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear隊(duì)滿標(biāo)志是：f=(r+1)%N5.【統(tǒng)考書P604-14】設(shè)循環(huán)隊(duì)列的容量為40〔序號(hào)從0到39〕，現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=19;②front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素多少個(gè)？答：用隊(duì)列長(zhǎng)度計(jì)算公式：(N＋r－f)%N①L=〔40＋19－11〕%40=8②L=〔40＋11－19〕%40=32五、閱讀理解〔每題5分，共20分。至少要寫出思路〕【嚴(yán)題集3.7①】按照四那么運(yùn)算加、減、乘、除和冪運(yùn)算〔↑〕優(yōu)先關(guān)系的慣例，并仿照教材例3-2的格式，畫出對(duì)以下算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程：A－B×C/D+E↑F答：【嚴(yán)題集3.3②】寫出以下程序段的輸出結(jié)果〔棧的元素類型SElemType為char〕。voidmain(){StackS;Charx,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〞?！緡?yán)題集3.12②】寫出以下程序段的輸出結(jié)果〔隊(duì)列中的元素類型QElemType為char〕。voidmain(){QueueQ;InitQueue(Q);Charx=’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〞。【嚴(yán)題集3.13②】簡(jiǎn)述以下算法的功能〔棧和隊(duì)列的元素類型均為int〕。voidalgo3(Queue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);};while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)展逆置。六、算法設(shè)計(jì)〔每題5分，共15分。至少要寫出思路〕【李春葆及嚴(yán)題集3.19④】假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧，編寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù)correct(exp,tag)；其中：exp為字符串類型的變量〔可理解為每個(gè)字符占用一個(gè)數(shù)組元素〕，表示被判別的表達(dá)式，tag為布爾型變量。答：用堆棧st進(jìn)展斷定，將(、[或{入棧，當(dāng)遇到}、]或)時(shí)，檢查當(dāng)前棧頂元素是否是對(duì)應(yīng)的(、[或{，假設(shè)是那么退棧，否那么返回表示不配對(duì)。當(dāng)整個(gè)算術(shù)表達(dá)式檢查完畢時(shí)，假設(shè)棧為空表示括號(hào)正確配對(duì)，否那么不配對(duì)。編程后的整個(gè)函數(shù)如下〔李書P31—32〕#definem0100/*m0為算術(shù)表達(dá)式中最多字符個(gè)數(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]==’)’)/*遇到’)’，假設(shè)棧頂是‘(‘，那么繼續(xù)處理，否那么以不配對(duì)返回*/if(st[top]==‘(‘)top--;elsetag=0;if(exp[i]==’)’)/*遇到’]’，假設(shè)棧頂是‘[‘，那么繼續(xù)處理，否那么以不配對(duì)返回*/if(st[top]==‘[‘]top--;elsetag=0;if(exp[i]==’)’)/*遇到’}’，假設(shè)棧頂是‘{‘，那么繼續(xù)處理，否那么以不配對(duì)返回*/if(st[top]==‘{‘top--;elsetag=0;i++;}if(top>0)tag=0;/*假設(shè)棧不空，那么不配對(duì)*/}嚴(yán)題集對(duì)應(yīng)答案：3.19StatusAllBrackets_Test(char*str)//判別表達(dá)式中三種括號(hào)是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'