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

1、一、填空題二、1.向量、棧和隊(duì)列都是 線性 結(jié)構(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

2、 .帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于 0 o解：I：4r ，head* I L=head | 頭結(jié) | R=head 產(chǎn)占八、二、判斷正誤（判斷下列概念的正確性，并作出簡(jiǎn)要的說(shuō)明。）三、（ X ） 1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù) 雜類型。錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)，與元素?cái)?shù)據(jù)類型無(wú)關(guān)。（X ） 2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用,CPU中也用隊(duì)列J。(，)3.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。( ，)4.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以

3、是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(X ) 5.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。(X ) 6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(，)7.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。(，)8.兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。(X ) 9.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，

4、是一種先進(jìn)后出型結(jié)構(gòu)。錯(cuò)，后半句不對(duì)。(X ) 10. 一個(gè)棧的輸入序列是12345 ,則棧的輸出序列不可能是12345。錯(cuò)，有可能。1 分，共 20 分)B ) 1. 棧中元素的進(jìn)出原則是A .先進(jìn)先出B.后進(jìn)先出 C.?？談t進(jìn)D.棧滿則出2( C ) 2.若已知一個(gè)棧的入棧序列是1, 2, 3,，n,其輸出序列為pl, p2, p3,pn ，若 p1=n ，則 pi 為A. i B. n=i C. n-i+1D.不確定解釋：當(dāng) p1=n ，即 n 是最先出棧的，根據(jù)棧的原理， n 必定是最后入棧的( 事實(shí)上題目已經(jīng)表明了)，那么輸入順序必定是 1,2,3,，n,則出棧的序列是 n,，3,

5、2, 1。(若不要求順序出棧，則輸出序列不確定)( B ) 3. 判定一個(gè)棧ST (最多元素為m0 )為空的條件是A. ST->top<>0 B . ST->top=0 C. ST->top<>m0 D. ST->top=m0( A ) 4. 判定一個(gè)隊(duì)列 QU (最多元素為 m0 )為滿隊(duì)列的條件是A. QU->rear-QU->front = = m0 B . QU->rear QU->front - 1= = m0 C . QU->front=QU->rear D . QU->front = = Q

6、U->rear+1解：隊(duì)滿條件是元素個(gè)數(shù)為m0o由于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1,所以不必再減1 了，應(yīng)當(dāng)選 A。當(dāng)然，更正確的答案應(yīng)該取模，即： QU->front = = (QU->rear+1)% m0( D )5.數(shù)組Q ：n用來(lái)表示一個(gè)循環(huán)隊(duì)列，f為當(dāng)前隊(duì)列頭元素的前一位置，r為隊(duì)尾元素的位置， 假定隊(duì)列中元素的個(gè)數(shù)小于n ,計(jì)算隊(duì)列中元素的公式為(A) rf;(B) (n + fr) % n;(C) n + rf;(D) (n+rf) % n設(shè)有 4 個(gè)數(shù)據(jù)元素a1 、 a2 、 a3 和 a4 ，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按al、a

7、2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?；蜿?duì)的初始狀態(tài)都是空?，F(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è)。供選擇的答案：AD：al a2a3 a4E: 1230答：ABCDE =2,4, 1, 2,27 .從供選擇的答案中，選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答,把相應(yīng)編號(hào)寫(xiě)在答 卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是

8、 A。設(shè)用一維數(shù)組 A1,川來(lái)表示一個(gè)棧，An為棧 底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH ） 一個(gè)新元素時(shí)， 變量T的值 B ;從棧中彈出（POP） 一個(gè)元素時(shí)，變量 T的值 C 。設(shè)棧空時(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,aE：n+1n+2nb,ac,bn-1n-211答案：ABCDE=2, 2, 1, 6, 4注意，向

9、地址的高端生長(zhǎng)，稱為向上生成堆棧；向地址低端生長(zhǎng)叫向下生成堆棧，本題中底部為n,向地址的低端遞減生成，稱為向下生成堆棧。8 .從供選擇的答案中，選出應(yīng)填入下面敘述?內(nèi)的最確切的解答,把相應(yīng)編號(hào)寫(xiě)在答卷的對(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+1下溢n/2D:長(zhǎng)度 深度 棧頂E:兩個(gè)棧的棧頂同

10、時(shí)到達(dá)?？臻g的中心點(diǎn)兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇一個(gè)棧的棧底答案：ABCDE =2, 1, 2, 4, 3棧底其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另四、簡(jiǎn)答題（每小題 4分，共20分）1. 說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(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 。 用途不同，

11、堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于 多道作業(yè)處理 、指令寄存及其他運(yùn)算2. 設(shè)有編號(hào)為 1 ， 2 ， 3 ， 4 的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫(xiě)出這四輛列 車開(kāi)出車站的所有可能的順序。種： 4,3,2,13 種，3,4,2,13,2,4,15 種， 2,4,3,12,3,4,15 種，1,4,3,21,3,2,43,2,1,42,1, 3,42,1,4,32, 3,1,41,3,4,21, 2,3,41,2,4,3答：至少有14 種。 全進(jìn)之后再出情況，只有1 進(jìn)3個(gè)之后再出的情況，有 進(jìn)2個(gè)之后再出的情況，有 進(jìn)1個(gè)之后再出的情況，有3. 假設(shè)正讀和反讀都相同的字符序列為

12、 “ 回文” ， 例如， abba 和 abcba 是回文， abcde 和 ababab 則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等 方式正確輸出其回文的可能性？答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（ j- ）從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_(kāi)到數(shù)組末尾，然后直接用 POP 動(dòng)作實(shí)現(xiàn)。 （但堆棧是先減后壓還是）若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開(kāi)輔助空間，可以從鏈?zhǔn)组_(kāi)始入棧，全部 壓入

13、后再依次輸出。4. 順序隊(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. 設(shè)循環(huán)隊(duì)列的容量為 40 （序號(hào)從 0 到 39

14、） ，現(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= （401911 ） % 40=8 L= （4011 19） % 40=32五、閱讀理解（每小題 5 分，共 20 分。至少要寫(xiě)出思路）1 . 寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類型SElem Type 為 char ） 。void main( )Stack S;Char x,y;InitStack(S);X= c ;y= k ;Push(S,x); Push(S, a ); P

15、ush(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 ” 。2 .嚴(yán)嚴(yán)題集3.12】寫(xiě)出下列程序段的輸出結(jié)果(隊(duì)列中的元素類型QElem Type為char)。void main( )Queue Q; Init Queue (Q);Char x= e ; y= c ;EnQueue (Q, h ); EnQueue (Q, r ); EnQueue (Q, y);DeQueue (Q,x); E

16、nQueue (Q,x);DeQueue (Q,x); EnQueue (Q, a );while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答：輸出為“charint) 。3. 簡(jiǎn)述以下算法的功能(棧和隊(duì)列的元素類型均為void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q)DeQueue (Q,d); Push(S,d);while(!StackEmpty(S)Pop(S,d); EnQueue (Q,d);答：該算法的功能是：利用堆棧做輔助，

17、將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。六、算法設(shè)計(jì)(每小題 5 分，共 15 分。至少要寫(xiě)出思路)1. 假設(shè)一個(gè)數(shù)組squm 存放循環(huán)隊(duì)列的元素。 若要使這 m 個(gè)分量都得到利用， 則需另一個(gè)標(biāo)志 tag ，以 tag 為 0 或 1 來(lái)區(qū)分尾指針和頭指針值相同時(shí)隊(duì)列的狀態(tài)是“ 空” 還是“ 滿” 。試編寫(xiě)相應(yīng)的入隊(duì)和出隊(duì)的算法。解：這就是解決隊(duì)滿隊(duì)空的三種辦法之設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空(其他兩種見(jiàn)簡(jiǎn)答題) ；思路：一開(kāi)始隊(duì)空，設(shè)tag=0 ，若從 rear 一端加到與front 指針相同時(shí)，表示入隊(duì)已滿，則令tag=1 ；若從 front 一端加到與rear 指針相同時(shí)，則令tag=0 ，表示出隊(duì)已空。2. 試寫(xiě)一個(gè)算法