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

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

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

3、用隊列。（V ） 3.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進 先出型結(jié)構(gòu)。（V ） 4.對于不同的使用者，一個表結(jié)構(gòu)既可以是棧，也可以是隊列，也可以是線性 表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（X ） 5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。借，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲結(jié)構(gòu)概念，二者不是同類項。（X ） 6.棧和隊列是一種非線性數(shù)據(jù)結(jié)構(gòu)。借，他們都是線性邏輯結(jié)構(gòu)，棧和隊列其實是特殊的線性表，對運算的定義略有不同而已。（V ） 7.棧和隊列的存儲方式既可是順序方式，也可是鏈接方式。（V ） 8.兩個棧共享

4、一片連續(xù)內(nèi)存空間時，為提高內(nèi)存利用率，減少溢出機會，應(yīng)把 兩個棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（X ） 9.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié) 構(gòu)。借，后半句不對。(X ) 10. 一個棧的輸入序列是12345,則棧的輸出序列不可能是12345c 錯,有可能。三、單項選擇題(每小題1分，共20分)(B ) 1. K00年元月統(tǒng)考題棧中元素的進出原則是A.先進先出 B.后進先出 C.棧空則進D.棧滿則出(C ) 2. K李春葆若已知一個棧的入棧序列是1, 2, 3,，11,其輸出序列為pl, p2, p3,，pn,若 pl=n,則 pi 為A. i B. n

5、=i C. n-i+1D.不確定解釋：當pl=n,即n是最先出棧的，根據(jù)棧的原理，n必定是最后入棧的，那么輸入順序 必定是1, 2, 3,，n,則出棧的序列是n,，3, 2, 1。(B ) 3. K李春葆判定一個棧ST (最多元素為mO)為空的條件是A . ST->top<>0B . ST->top=0C . ST->top<>mOD. ST->top=mO(B ) 4. K李春葆判定一個隊列QU (最多元素為mO)為滿隊列的條件是A . QU->iear QU->fiont = = mO B . QU->rear QU->

6、;fiont 1= mOC . QU->fiont = = QU->rearD . QU->fiont = = QU->rear+l(D ) 5.數(shù)組Q n 用來表示一個循環(huán)隊列，f為當前隊列頭元素的前一位置，r為隊尾元素的位置，假定隊列中元素的個數(shù)小于n,計算隊列中元素的公 式為(A ) 1f;( B ) (n+f-i ) % n; ( C ) n+if;( D ) (n+r-f) %n6. 【98初程P71 從供選擇的答案中，選出應(yīng)填入下面敘述_內(nèi)的最確切的解答, 把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個數(shù)據(jù)元素al、a2、a3和a4,對他們分別進行棧操作或隊操作。在

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

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

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

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

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

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

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

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

15、t ）優(yōu)先關(guān)系的慣例，并仿 照教材例32的格式，畫出對卞列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程：AEXC/D+E t F序號()PTR 棧OPND 棧當前字符備注AB#c/D+EAFn（操作）1push(OPND/A,)2#Apush(OPTR/-f)3# Apush(OPND/Br)4n-ABpush(OPTR/ *z)5ABpushCOPND/CO6# 一類ABC歸約令T> = B*C7# -AT,pushCOPTR/f)8#-AT.push(OPND/Df)9«-/ATiD歸約令T: = T./D10»-/AT2歸約，令Tj = A-Tz11t2push

16、(OPTR/4-r)12« +t3push(OPND/E#)13# +t3epush()PTR/ f F)14# + *t3epush (OPND/D15# +豐t3ef歸約令T4=Ef F16# +t3t4歸約令t5=t,+t417#Tsreturn(T$)2. 【嚴題集3.3】寫出下列程序段的輸出結(jié)果(棧的元素類型SElemType為chai)。 void main()Stack S;Clw x,y；IiutStack(S);X=C;y=上；Push(S,x); Push(S,W); Push(S,y);Pop(S,x); Push(S；f); Push(S?x);Pop(S,x

17、); Push(S,s,);wlule(? StackEniptv(S) Pop(S、y);pnntf(y); ;Printf(x);答：輸出為“stack”。3. 【嚴題集3.12】寫出卞列程序段的輸出結(jié)果(隊列中的元素類型QElemType為char)。 void main()Queue Q; Init Queue (Q);Char x='e'y='c：EnQueue (Q/1V); EnQueue (Q/r5); EnQueue (Q,y);lf(sttop= ='C ) top;else tag=0;if (expi= =5 y )/*遇到訂，若棧頂是十

18、，則繼續(xù)處理，否則以不配對返回*/if(sttop= = top;else tag=0;if(expi=>)9/*遇到),若棧頂是則繼續(xù)處理，否則以不配對返回*/if(sttop= =cc top-;else tag=0;1+;if(top>0)tag=0; /*若棧不空，則不配對*/嚴題集對應(yīng)答案：3.19Status AllBrackets_Test(cliar *str)判別表達式中三種括號是否匹配LutStack(s);for(p=str;*p;p-H-)if(*P='(1l*P=''H*P='') push(s,*p);else if(*p=，)1|*p=T|*p=T)if(StackEmptv(s) retiim ERROR;pop(s,c);&c!=() return ERROR;if(*p=T&&c!=T) return ERROR;if(*p=丁&&c!=) r