第4章棧與隊(duì)列自測(cè)卷答案

1、棧和隊(duì)列一、填空題（每空1 分，共15 分）1.向量、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在向量的 任何頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為位置插入和刪除元素；對(duì)于棧只能在隊(duì)首刪除元素。棧頂。不允許插入和刪除運(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í)，其操作是先移

2、動(dòng)隊(duì)首指針，后取出元素 。8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長(zhǎng)度等于0。解：headL=head頭結(jié)點(diǎn)R=head二、判斷正誤（判斷下列概念的正確性，并作出簡(jiǎn)要的說明。（每小題 1 分，共 10 分）（×） 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ù)類型無關(guān)。（×） 2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU 中也用隊(duì)列。（） 3. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（） 4. 對(duì)于不同

3、的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。（ ×） 5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。（×）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)存空間的兩端。（ ×

4、;） 9. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯(cuò)，后半句不對(duì)。（× ） 10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯(cuò)，有可能。三、單項(xiàng)選擇題（每小題 1 分，共 20 分）（ B ） 1.棧中元素的進(jìn)出原則是（C）2.先進(jìn)先出若已知一個(gè)棧的入棧序列是后進(jìn)先出1， 2， 3， ，棧空則進(jìn)n，其輸出序列為棧滿則出p1，p2， p3， ， pn，若p1=n，則pi為 i n=i n-i+1不確定解釋：當(dāng)p1=n，即 n 是最先出棧的，根據(jù)棧的原理，n 必定是最后入棧的（事實(shí)上題目已經(jīng)表明了），那么輸入順序必定是1， 2，

5、3， ， n，則出棧的序列是n， ， 3，2， 1。（若不要求順序出棧，則輸出序列不確定）（ B ） 3.判定一個(gè)棧ST（最多元素為m0）為空的條件是 ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0（ A ） 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+

6、1解：隊(duì)滿條件是元素個(gè)數(shù)為m0。由于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1，所以不必再減1 了，應(yīng)當(dāng)選A 。當(dāng)然，更正確的答案應(yīng)該取模，即：QU->front = = (QU->rear+1)% m0（ D ） 5數(shù)組用來表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為（） r f;（）（ n f r） % n;（） n r f;（）（ n r f） % n6.從供選擇的答案中，選出應(yīng)填入下面敘述？?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ì)操作。

7、在進(jìn)棧或進(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 a3a4E：1230答： ABCDE 2,4,1,2,27.從供選擇的答案中，選出應(yīng)填入下面敘述？?jī)?nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表

8、，它的特點(diǎn)是A。設(shè)用一維數(shù)組A1,n來表示一個(gè)棧，An 為棧底，用整型變量 T 指示當(dāng)前棧頂位置， AT 為棧頂元素。往棧中推入（ PUSH）一個(gè)新元素時(shí)，變量 T 的值 B ；從棧中彈出（ POP）一個(gè)元素時(shí)，變量 T 的值 C 。設(shè)棧空時(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,bb,c c,ab,a c,b a,cE：n+1n+2 n n-1 n-2答案： ABCDE=2,2,1,

9、6,4注意，向地址的高端生長(zhǎng)， 稱為向上生成堆棧； 向地址低端生長(zhǎng)叫向下生成堆棧， 本題中底部為n，向地址的低端遞減生成，稱為向下生成堆棧。8.從供選擇的答案中，選出應(yīng)填入下面敘述？?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ā)生上溢，則說明該棧的最大容量為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

10、： 長(zhǎng)度深度 棧頂 棧底E：兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)兩個(gè)棧的棧頂在達(dá)棧空間的某一位置相遇兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案： ABCDE 2,1, 2, 4,3四、簡(jiǎn)答題（每小題4 分，共 20 分）1.說明線性表、棧與隊(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)算

11、，因而是先進(jìn)先出表FIFO 。 用途不同，堆棧用于子程調(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)的車站，具體寫出這四輛列車開出車站的所有可能的順序。劉答：至少有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,4 2,1,4,32,1,3,4 進(jìn) 1個(gè)之后再出的情況，有5種， 1,4,3,21,3,2,41,3,4,2 1, 2,3,41,2,

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