數(shù)據(jù)結(jié)構(gòu)作業(yè)：第三章棧和隊(duì)列作業(yè)答案

1、第三章 棧和隊(duì)列一 選擇題1. 對(duì)于棧操作數(shù)據(jù)的原則是（ B ）。A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否( B ),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否( A)。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為( B )。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 ( D)分別設(shè)在這片內(nèi)存空間的兩端,這樣,當(dāng)( C )時(shí)，才產(chǎn)生上溢。, : A. 空 B. 滿(mǎn) C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D.n/2 : A. 長(zhǎng)度 B. 深度 C. 棧頂 D.

2、棧底 : A. 兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn).B. 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn). C. 兩個(gè)棧的棧頂在?？臻g的某一位置相遇. D. 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.3. 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1=i=n）個(gè)元素是（ B ）。A. 不確定 B. n-i+1 C.i D. n-i4. 若一個(gè)棧的輸入序列為1,2,3,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（ D ）。A. i-j-1 B. i-j C. j-i+1 D. 不確定的5. 若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN

3、是n，則pi是( D )。 A. iB. n-i C. n-i+1 D. 不確定6. 有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（C ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 67. 設(shè)棧的輸入序列是1，2，3，4,則（D ）不可能是其出棧序列。A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2，D. 4，3，1，2， E. 3，2，1，4，8. 一個(gè)棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ B ）。 A. 2 3 4 1 5 B.

4、5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 29. 設(shè)一個(gè)棧的輸入序列是 1，2，3，4，5,則下列序列中，是棧的合法輸出序列的是（ D ）。A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 410. 某堆棧的輸入序列為a, b，c ，d,下面的四個(gè)序列中，不可能是它的輸出序列的是（ D ）。 A. a，c，b，dB. b, c，d，a C. c, d，b, a D. d, c，a，b11. 設(shè)abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作,則下面得不到的序列為（D ）。Afedcba B. bcafed C

5、. dcefba D. cabdef12. 設(shè)有三個(gè)元素X，Y，Z順序進(jìn)棧（進(jìn)的過(guò)程中允許出棧），下列得不到的出棧排列是( C )。AXYZ B. YZX C. ZXY D. ZYX13. 輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為（ B ）A.push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop14. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m，topi代表第i個(gè)棧( i =1,2)棧頂，棧1的底在v1，

6、棧2的底在Vm，則棧滿(mǎn)的條件是（B ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D.top1=top215. 設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ D ）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧16. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ D）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改17. 用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( D )。A僅修改隊(duì)頭指針

7、B. 僅修改隊(duì)尾指針C. 隊(duì)頭、隊(duì)尾指針都要修改 D. 隊(duì)頭,隊(duì)尾指針都可能要修改18. 棧的特點(diǎn)是（ ）,隊(duì)列的特點(diǎn)是（ ）,棧和隊(duì)列都是（ ）。若進(jìn)棧序列為1,2,3,4 則（ ）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為1,2,3,4 則（ ）是一個(gè)出隊(duì)列序列。BACCF, : A. 先進(jìn)先出 B. 后進(jìn)先出 C. 進(jìn)優(yōu)于出 D. 出優(yōu)于進(jìn): A.順序存儲(chǔ)的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu) D.限制存取點(diǎn)的非線性結(jié)構(gòu), : A. 3,2,1,4 B.3,2,4,1 C. 4,2,3,1 D. 4,3,2,1F. 1,2,3,4 G. 1,3,

8、2,419. 棧和隊(duì)都是（C ）A順序存儲(chǔ)的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C. 限制存取點(diǎn)的線性結(jié)構(gòu) D. 限制存取點(diǎn)的非線性結(jié)構(gòu)二 判斷題1兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（ ）2. 即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（ ）3. 隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（ ）4. 隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。（ ）5. 循環(huán)隊(duì)列也存在空間溢出問(wèn)題。（ ）6. 隊(duì)列和棧都是運(yùn)算受限的線性表，只允

9、許在表的兩端進(jìn)行運(yùn)算。（ ）7. 棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（ ）8. 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。?）四 應(yīng)用題1. 名詞解釋?zhuān)簵！㈥?duì)列、循環(huán)隊(duì)列？棧是只準(zhǔn)在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱(chēng)后進(jìn)先出（LIFO）表。隊(duì)列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊(duì)尾，允許刪除的一端叫隊(duì)頭。最先插入隊(duì)的元素最先離開(kāi)（刪除），故隊(duì)列也常稱(chēng)先進(jìn)先出（FIFO）表。循環(huán)隊(duì)列：用常規(guī)意義下順序存儲(chǔ)結(jié)構(gòu)的一維數(shù)組表示隊(duì)列，由于隊(duì)列的性質(zhì)（隊(duì)尾插入和隊(duì)頭刪除），容易造成“假溢出”現(xiàn)象，即隊(duì)尾已到達(dá)一維數(shù)組的高下標(biāo)，不能再插入，然而隊(duì)中元素個(gè)數(shù)小于隊(duì)列的長(zhǎng)度（容量）。循環(huán)隊(duì)列是解決“假溢出”的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊(duì)列下，通常采用“犧牲一個(gè)存儲(chǔ)單元”或“作標(biāo)記”的方法解決“隊(duì)滿(mǎn)”和“隊(duì)空”的判定問(wèn)題2. 簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿(mǎn)和空的條件。假溢出避免方法：采取循環(huán)隊(duì)列的形式。3. 怎樣判定循環(huán)隊(duì)列的空和滿(mǎn)？在循環(huán)隊(duì)列下，仍定義front=rear時(shí)為隊(duì)空，