第三章棧和隊(duì)列.doc

第三章 棧和隊(duì)列一選擇題 1棧與一般線性表的區(qū)別在于_。 A數(shù)據(jù)元素的類(lèi)型不同 B運(yùn)算是否受限制 C數(shù)據(jù)元素的個(gè)數(shù)不同 D邏輯數(shù)據(jù)不同 分析：該題目主要考查棧的定義。棧屬于特殊的線性表，特殊性在于其刪 除和插入操作只能夠在棧頂進(jìn)行，是一種運(yùn)算受到限制的線性表。答案為 。 2一個(gè)順序棧旦被聲明，其占用空間的大小_。 A已固定 B可以改變 C不能固定 D動(dòng)態(tài)變化 分析：該題目主要考查順序棧存儲(chǔ)結(jié)構(gòu)的特點(diǎn)。順序棧用數(shù)組實(shí)現(xiàn)，因此 一旦順序棧被聲明，則其空間大小固定。答案應(yīng)選擇 A。 3設(shè)有順序棧 S，元素 s1,s2,s3,s4,s5,s6 依次進(jìn)棧，如果 6 個(gè)元素出 棧的順序是 s2,s4,s3,s6,s5,s1，則棧的容量至少應(yīng)該是_。 A3 B4 C5 D6 分析：該題目主要考查順序棧的存儲(chǔ)空間定義。當(dāng) s2 出棧時(shí)，則棧的容量 為 2(s1,s2 在棧中)；當(dāng) s4 出棧時(shí)，則棧的容量為 3(s1,s3,s4 在棧中)； 當(dāng) s6 出棧時(shí)，則棧的容量為 3(s1,s5,s6 在棧中)；因此棧的最小容量應(yīng)為 3。答案應(yīng)選擇 A。 4 從一個(gè)棧頂指針為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪除的 結(jié)點(diǎn)，執(zhí)行_。 Ax=top-data；top=top-next； Btop=top-next；x=top； Cx=top-data； Dx=top；top=top-next； 分析： 該題目主要考查鏈棧的具體操作。首先將指針變量 x 保存被刪除結(jié)點(diǎn)，然后調(diào)整棧頂指針(top=top-next)。選項(xiàng) A 中，x=top-data 操作目 的是將棧頂結(jié)點(diǎn)的元素值賦給 x，故無(wú)法滿足題目要求。選項(xiàng) B 中，首先進(jìn) 行棧頂指針 top 調(diào)整，則 x 保存的不是當(dāng)前刪除的結(jié)點(diǎn)，而是棧調(diào)整后的 棧頂元素。因此答案應(yīng)選擇 D。 5在個(gè)棧頂指針為 top 的鏈棧中，將一個(gè) s 指針?biāo)傅慕Y(jié)點(diǎn)入棧，執(zhí)行 _。 Atop-nexts： B s-next=top-next; top-next=s; Cs-next=top; tops； Ds-next=top; top=top-next; 分析：該題目主要考查鏈棧的具體操作。根據(jù)鏈棧入棧操作定義，即可得 到答案。答案為 C。從選擇題 4、5 可以看出，鏈棧的入棧和出棧操作實(shí)質(zhì) 上是對(duì)沒(méi)有頭結(jié)點(diǎn)的單鏈表進(jìn)行插入與刪除操作。 6鏈棧和順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)，即_。 A插入操作更加方便 B通常不會(huì)出現(xiàn)棧滿的情況 C不會(huì)出現(xiàn)?？盏那闆r D刪除操作更加方便 分析： 該題目主要考查鏈棧和順序棧的特點(diǎn)。 棧的兩種存儲(chǔ)方式各有特點(diǎn)， 即順序棧所需存儲(chǔ)空間較少，但棧的大小受數(shù)組的限制；鏈棧由于每個(gè)結(jié) 點(diǎn)都包含數(shù)據(jù)域和指針域，則所需空間相對(duì)較大，但棧的大小不受限制(受 內(nèi)存容量的限制)。所以答案為 B。對(duì)順序棧而言，其插入操作(入棧)不需 要大量地移動(dòng)元素，故插入操作(入棧)則不是鏈棧的優(yōu)點(diǎn)，因此 A 選項(xiàng)說(shuō) 法有問(wèn)題。 7用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的_位置。 A鏈頭 B鏈尾 C鏈中 D任意位置 分析：該題目主要考查鏈?zhǔn)疥?duì)列的存儲(chǔ)結(jié)構(gòu)，如圖 3.2 所示。隊(duì)列的隊(duì)頭 是對(duì)隊(duì)列元素進(jìn)行刪除的一端，鏈隊(duì)列的隊(duì)頭在鏈表的鏈頭位置。 (不考慮不包含數(shù)據(jù)元素的頭結(jié)點(diǎn))，答案為 A。 圖 3.2 鏈?zhǔn)疥?duì)列 8在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù) 據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則從該緩沖 區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)_結(jié)構(gòu)。 A堆棧 B隊(duì)列 C數(shù)組 D線性表 分析：該題目主要考查隊(duì)列的性質(zhì)和應(yīng)用。緩沖區(qū)中的數(shù)據(jù)應(yīng)該是先到達(dá) 的先打印，所以使用具有 FIFO 性質(zhì)的隊(duì)列來(lái)實(shí)現(xiàn)。答案為 B。 9做入棧運(yùn)算時(shí)，應(yīng)先判斷棧是否為 (1) ，做出棧運(yùn)算時(shí)，應(yīng)先判 斷棧是否為 (2) 。當(dāng)順序棧中元素為 n 個(gè)，做入棧運(yùn)算時(shí)發(fā)生上溢， 則說(shuō)明該棧的最大容量為 (3) 。為了增加內(nèi)存空間的利用率和減少發(fā) 生上溢的可能性，由兩個(gè)順序棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 (4) 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) (5) 時(shí)，才產(chǎn)生上 溢。 (1)、(2)A空 B滿 C上溢 D下溢 (3) An-l Bn Cn1 Dn2 (4) A長(zhǎng)度 B深度 C棧頂 D棧底 (5) A兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) B其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn) C兩個(gè)棧的棧頂在?？臻g的某一位置相遇 D兩個(gè)棧均不為空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底 分析：該題目主要考查棧的性質(zhì)、結(jié)構(gòu)和操作。答案為：(1)B (2)A (3)B a1 a2 . an front rear(4) D (5) C 10 若已知一個(gè)棧的入棧序列是 l,2,3, ,30 ， 其輸出序列是 p1,p2,p3,pn，若 p130，則 p10 為_(kāi)。 A 11 B 20 C 30 D 2l 分析：該題目主要考查棧的性質(zhì)、結(jié)構(gòu)和操作。已知數(shù)據(jù)的入棧序列是 l， 2，3，30，出棧序列的第 1 個(gè)元素是 30，因此可以確定，所有元素是 按入棧序列順序全部入棧之后才開(kāi)始出棧的。也就是說(shuō)，出棧序列與入棧 序列剛好相反，可求得出棧序列的第 10 個(gè)元素為 21，即 D 答案正確。 11循環(huán)隊(duì)列 Am存放其元素，用 front 和 rear 分別表示隊(duì)頭及隊(duì)尾，則 循環(huán)隊(duì)列滿的條件是_。 A(Q-rear+1)%m=Q-front BQ-rear=Q-front+1 CQ-rear+1=Q-front DQ-rear=Q-front 分析：該題目主要考查循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)以及隊(duì)滿的判斷條件。循環(huán)隊(duì) 列的引入是為了解決隊(duì)列存在的“假溢出”問(wèn)題，但在循環(huán)隊(duì)列中會(huì)出現(xiàn) 隊(duì)滿和隊(duì)空的判斷條件相同而導(dǎo)致無(wú)法判斷，通常采用少用一個(gè)元素空間 的策略來(lái)解決該問(wèn)題(其它策略講解請(qǐng)參考配套教材)。 使隊(duì)尾指針 Q-rear 無(wú)法趕上 Q-front，即隊(duì)尾指針加 1 就會(huì)從后面趕上隊(duì)頭指針，這種情況 下隊(duì)滿的條件是：(Q-rear+1) %m= Q-front。答案是 A。 12 設(shè)數(shù)組 datam作為循環(huán)隊(duì)列 sq 的存儲(chǔ)空間， front 為隊(duì)頭指針， rear 為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針 front 值為_(kāi)。 Afront=front+1 Bfront=(front+1)%(m-1) Cfront=(front-1)%m Dfront=(front+1)%m 分析：該題目主要考查循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)和出隊(duì)操作。隊(duì)列的頭指針指 向隊(duì)首元素的實(shí)際位置，因此出隊(duì)操作后，頭指針需向上移動(dòng)一個(gè)元素的 位置。根據(jù)第 11 題的解答可知，循環(huán)隊(duì)列的容量為 m，所以頭指針 front加 1 以后，需對(duì) m 取余，使之自動(dòng)實(shí)現(xiàn)循環(huán)，即當(dāng) front 取到最大下標(biāo)(m-1 處)以后，自動(dòng)循環(huán)回來(lái)取 0 值。所以答案是 D。 13由兩個(gè)棧共享一個(gè)向量空間的好處是_ 。 A減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B節(jié)省存儲(chǔ)空間，降低上溢 發(fā)生的機(jī)率 C減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D節(jié)省存儲(chǔ)空間，降低下溢 發(fā)生的機(jī)率 分析：該題目主要考查對(duì)順序棧存儲(chǔ)結(jié)構(gòu)的理解。兩個(gè)棧無(wú)論是共享向量 空間還是單獨(dú)分配空間，對(duì)它們的操作所需的時(shí)間沒(méi)有影響。兩個(gè)棧共享 向量空間，主要是為了節(jié)省存儲(chǔ)空間，降低上溢的發(fā)生機(jī)率，因?yàn)楫?dāng)一個(gè) 棧中的元素較少時(shí)，另一個(gè)?？捎每臻g可以超過(guò)向量空間的一半。答案應(yīng) 選擇 B。 14若用單鏈表來(lái)表示隊(duì)列，則應(yīng)該選用_。 A帶尾指針的非循環(huán)鏈表 B帶尾指針的循環(huán)鏈表 C帶頭指針的非循環(huán)鏈表 D帶頭指針的循環(huán)鏈表 分析：本題主要考查讀者對(duì)循環(huán)單鏈表存儲(chǔ)結(jié)構(gòu)和隊(duì)列定義的理解。設(shè)尾 指針 rear，則通過(guò) rear 可以訪問(wèn)隊(duì)尾，通過(guò) rear-next 可以訪問(wèn)隊(duì)頭， 因此帶尾指針的循環(huán)鏈表較適合。答案應(yīng)選擇 B。 二判斷題 1消除遞歸不一定需要使用棧，此說(shuō)法是否正確。 正確 分析：該題目主要考查棧在遞歸中的應(yīng)用。對(duì)于尾遞歸可以將其轉(zhuǎn)化成遞 推，不需棧。所以這種說(shuō)法是正確的。 尾遞歸是指一個(gè)遞歸函數(shù)的遞歸調(diào)用語(yǔ)句是遞歸函數(shù)的最后一句可執(zhí)行語(yǔ)句。 例如下面是一個(gè)輸出數(shù)組元素的遞歸函數(shù)。 void RPrintArray(int list,int n) if(n=0) printf(“%d”,listn); RPrintArray(list,-n); 此程序是尾遞歸程序，消除尾遞歸很簡(jiǎn)單，只需首先計(jì)算新的 n 值， n=n-1，然后程序轉(zhuǎn)到函數(shù)的開(kāi)始處執(zhí)行就行了，可以使用 while 語(yǔ)句來(lái)實(shí) 現(xiàn)。 相應(yīng)非遞歸函數(shù)如下： void PrintArray(int list,int n) while (n=0) printf(“%d”,listn); -n; 2棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。 正確 分析：該題目主要考查棧和隊(duì)列的定義。它們都只能在一端或兩端存取數(shù)據(jù)的線性結(jié)構(gòu)。見(jiàn)選擇題第 1 題解答。 3入棧操作、出棧操作算法的時(shí)間復(fù)雜性均為 O(n)。 錯(cuò)誤 分析：該題目主要考查棧的操作算法。入棧與出棧操作都在確定的棧頂位 置進(jìn)行，算法的時(shí)間復(fù)雜性均為 O(1)。所以這種說(shuō)法是錯(cuò)誤的。 4隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。 錯(cuò)誤 分析：該題目主要考查隊(duì)列的邏輯結(jié)構(gòu)和操作。隊(duì)列是上端只能進(jìn)行入隊(duì) 操作(即增加操作)，下端只能進(jìn)行出隊(duì)操作(即減少操作)。 5用 I 代表入棧操作，O 代表出棧操作，棧的初始狀態(tài)和棧的最終狀態(tài)都 為空，則使用棧的入棧和出棧可能出現(xiàn)的操縱序列為 IOIOIOOI。 錯(cuò)誤 分析：該題目主要考查棧的操作和“溢出”問(wèn)題。在棧的操作中，保證出 棧前提是棧中有元素，否則會(huì)造成棧的下溢，IOIOIOOI 會(huì)出現(xiàn)下溢。 6任何一個(gè)遞歸過(guò)程都可以轉(zhuǎn)換為非遞歸過(guò)程。 正確 分析：該題目主要考查棧在遞歸過(guò)程非遞歸化中的應(yīng)用。任何一個(gè)遞歸過(guò) 程都可以按照一定的步驟機(jī)械地轉(zhuǎn)換為非遞歸過(guò)程。由于棧的后進(jìn)先出特 性吻合遞歸算法的執(zhí)行過(guò)程，因而可以用非遞歸算法替代遞歸算法。遞歸 過(guò)程轉(zhuǎn)換為非遞歸過(guò)程的實(shí)質(zhì)就是將遞歸中隱含的棧機(jī)制轉(zhuǎn)化為由用戶直 接控制的棧，利用堆棧保存參數(shù)。 三填空題 1已知一個(gè)棧的輸入序列為 abcd，判斷下面兩個(gè)序列能否通過(guò)棧的 Push_Stack 和 Pop_Stack 操作輸出：(1)dbca (1) (2)cbda (2) 答案：(1)不能 (2)能 分析：該題目主要考查棧的操作。(1)不能，因?yàn)閺棾?d 時(shí)，abc 均已依次 壓入棧，下一個(gè)彈出的元素只能是 c 而不是 b。(2)能，Push_Stack (s,a)， Push_Stack (s,b)，Push_Stack (s,c)，Pop_Stack (s)，Pop_Stack (s)， Push_Stack (s,d), Pop_Stack (s), Pop_Stack (s)。 2對(duì)循環(huán)隊(duì)列 Q(設(shè)循環(huán)隊(duì)列空間大小為 MAXSIZE)，如何修改隊(duì)頭指針? (1) ； 如何修改隊(duì)尾指針? (2) 答案：(1)front=(front+1)% MAXSIZE (2)rear=(rear+1)% MAXSIZE 分析：該題目主要考查循環(huán)隊(duì)列的操作。具體解答請(qǐng)參見(jiàn)選擇題第 11 和 12 題。 3設(shè)長(zhǎng)度為 n 的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)列出隊(duì) 列操作的時(shí)間分別為 (1) 和 (2) ；若只設(shè)尾指針，則入隊(duì)列出隊(duì)列 操作的時(shí)間分別為 (3) 和 (4) 。 答案：(1)O(n) (2)O(n) (3)O(1) (4)O(1) 分析：該題目主要考查鏈隊(duì)列和單循環(huán)鏈表的綜合知識(shí)。當(dāng)只設(shè)頭指針時(shí) (如圖 3.3(a)所示)，入隊(duì)相當(dāng)于在 an 結(jié)點(diǎn)之后執(zhí)行結(jié)點(diǎn)插入操作，根據(jù)鏈 表的插入操作特點(diǎn)可知，插入操作前必須知道結(jié)點(diǎn) a1 和 an 的地址，獲取結(jié) 點(diǎn) an 的地址的時(shí)間復(fù)雜度為 O(n)；出隊(duì)則相當(dāng)于刪除結(jié)點(diǎn) a1 的操作，因此 必須獲取結(jié)點(diǎn) an 的地址，同樣其時(shí)間復(fù)雜度為 O(n)。若設(shè)置尾指針(如圖 3.3(b)，入隊(duì)相當(dāng)于在結(jié)點(diǎn) a1 之前和 an 之后執(zhí)行結(jié)點(diǎn)插入操作，通過(guò) rear 和 rear-next 可以獲得結(jié)點(diǎn) an 和 a1 的地址，則其時(shí)間復(fù)雜度為 O(1)；出 隊(duì)則相當(dāng)于刪除結(jié)點(diǎn) a1 的操作，同樣其時(shí)間復(fù)雜度為 O(1)。(a) (b) 圖 3.3 單循環(huán)鏈表表示的鏈隊(duì)列示意圖 4對(duì)于循環(huán)向量中的循環(huán)隊(duì)列，寫(xiě)出求隊(duì)列中元素個(gè)數(shù)的公式 _。 答案： (rear-frontMAXSIZE)% MAXSIZE，其中 MAXSIZE 表示隊(duì)列的存 儲(chǔ)空間。 分析：該題目主要考查循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)特點(diǎn)。 5向順序棧插入新元素分為三步：第一步，進(jìn)行 (1) 判斷，判斷條件 是 (2) ；第二步是修改 (3) ；第三步把新元素賦給 (4) 。同樣從 順序堆棧刪除元素分為三步；第一步，進(jìn)行 (5) 判斷，判斷條件是 (6) ；第二步是把 (7) 值返回；第三步 (8) 。 答案：(1)棧是否滿(2)s-top= MAXSIZE -1(3)棧頂指針(top+)(4)棧 頂對(duì)應(yīng)的數(shù)組元素(5)棧是否空(6)stop=-1(7)棧頂元素(8)修改棧頂指 針(top-) 分析：該題目是考慮棧的運(yùn)算規(guī)則及其入出棧的實(shí)現(xiàn)步驟。入棧時(shí)一般考 慮判斷棧滿否，條件是是否超出最大空間。如果沒(méi)有超出應(yīng)該修改棧頂指 針，然后將元素壓入堆棧。出棧時(shí)，應(yīng)首先考慮堆棧是否空。如果不空， 先保留棧頂元素，然后修改棧頂指針。 6在將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要 使用棧。對(duì)于前者，進(jìn)入棧的元素為表達(dá)式中的 (1) ，而對(duì)于后者，進(jìn) 入棧的元素為 (2) 。中綴表達(dá)式(a+b)/c-(f-d/e)所對(duì)應(yīng)的后綴表達(dá)式 a1 a2 . an head a1 a2 . an rear是 (3) 。 答案：(1)運(yùn)算符 (2)操作數(shù) (3)ab+c/fde/- 分析：該題目主要考查棧的應(yīng)用。中綴表達(dá)式就是將運(yùn)算符寫(xiě)于參與運(yùn)算 的操作數(shù)的中間，操作數(shù)依原序排列。后綴表達(dá)式就是將運(yùn)算符列于參與 運(yùn)算的操作數(shù)之后，操作數(shù)的排列依原序。因此計(jì)算后綴表達(dá)式值的過(guò)程 為：從左向右掃描后綴表達(dá)式，遇到操作數(shù)就進(jìn)棧，遇到運(yùn)算符就從棧中 彈出兩個(gè)操作數(shù)，執(zhí)行該運(yùn)算符所規(guī)定的運(yùn)算，并將所得結(jié)果進(jìn)棧。如此 下去，直到表達(dá)式結(jié)束。所以對(duì)于計(jì)算后綴表達(dá)式，進(jìn)棧的元素為操作數(shù)。 7假設(shè)以 S 和 X 分別表示入棧和出棧操作，則對(duì)輸入序列 a，b，e，d，e 進(jìn)行一系列棧操作 SSXSXSSXXX 之后，得到的輸出序列為_(kāi)。 答案：bceda 分析：該題目主要考查入棧和出棧操作。入棧和出棧操作只能在棧頂位置 進(jìn)行。根據(jù)操作序列，首先 a，b 進(jìn)棧，然后 b 出棧；接著 c 進(jìn)棧、c 出棧； d、e 相繼進(jìn)棧，棧頂元素為 e，最后 e、d、a 相繼出棧。這樣，得到出棧 序列為 bceda。 四應(yīng)用題 1將整數(shù) 1、2、3、4 依次入棧或出棧，請(qǐng)回答下述問(wèn)題： (1)當(dāng)入、出棧次序?yàn)?Push_Stack(S，1)、Pop_Stack(S)、Push_Stack(S， 2)、Push_Stack(S，x3)、Pop_Stack(S)、Push_Stack(S，4)、Pop_Stack(S)， 出棧的數(shù)字序列為何？ (2)能否得到出棧序列1423和1432？并說(shuō)明為什么不能得到或者如何得到。 (3)設(shè)有 n 個(gè)數(shù)據(jù)元素的序列順序進(jìn)棧，試給出可能輸出序列的個(gè)數(shù)和不可 能輸出序列的個(gè)數(shù)。當(dāng) n=4(1、2、3、4)有 24 種排列，哪些序列是可以通 過(guò)相應(yīng)的入出棧操作得到的。分析與解答：該題目主要考查棧的性質(zhì)、結(jié)構(gòu)和操作。 (1) 出棧序列為 l、3、4。 (2) 序列 1、4、2、3 不可能得到。因?yàn)?4 和 2 之間隔了 3，當(dāng) 4 出棧 后， 棧頂元素是 3， 而 2 在 3 的下面。 序列 1、 4、 3、 2 可以得到： Push_Stack(S， 1)、Pop_Stack(S)、Push_Stack(S，2)、Push_Stack(S，3)、Push_Stack(S， 4)、Pop_Stack(S)、Pop_Stack(S)、Pop_Stack(S)。 (3) 設(shè)有 n 個(gè)數(shù)據(jù)元素的序列(假設(shè)這個(gè)序列為 1，2，3，4，5n) 順序進(jìn)棧，那么輸出序列個(gè)數(shù) f(n)可以遞推求出：為討論方便, 設(shè) n=0, f(0)=1，當(dāng)， n=1：顯然 f(1)=1 n=2：容易得知 f(2)=2 n=3：1 最后出棧的序列有 f(2)種，2 最后出棧的序列有 f(1)* f(1)種， 3 最后出棧的序列有 f(2)種，所以 f(3)=2* f(2)+f(1)*f(1)=5 n=4：1 最后出棧的序列有 f(3)種，2 最后出棧的序列有 f(1)* f(2) 種，3 最后出棧的序列有 f(2)*f(1)種，4 最后出棧的序列有 f(3)種，所以 f(4)= 2*f(3)+ f(1)* f(2)+ f(2)* f(1)=14 可以看出 i(i=1,2,3,n)最后出棧的序列有 f(i-1)*f(n-i) 所以 f(n)=f(0)*f(n-1)+ f(1)*f(n-2)+f(2)*f(n-3)+f(3)*f(n-4)+ + f(n-1)*f(0)，用數(shù)學(xué)方法可得到 f(n)= ( ) ( )! n 2n ! n ! 2n 1 n 1 C 1 n 1 C 2nn n - + = + = 對(duì)有 n 個(gè)數(shù)據(jù)元素的序列，全部可能的排列個(gè)數(shù)為：Pn=n! 所以，不可能輸出序列的個(gè)數(shù)為：Pn-Cn。 因此 4 個(gè)元素的出棧序列數(shù)為：14 ! 4 ! 4 8 1 4 1 C 4 = + = ！ 這 14 種出棧序列如下： 1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 ( ) ( ) 2 n n! ! 2n 1 n 1 C + = 2試說(shuō)明下述運(yùn)算的結(jié)果 (1) Pop_Stack(Push_Stack(S，A)； (2) Push_Stack(S，Pop_Stack(S)； (3) Push_Stack(S，Pop_Stack(Push_Stack(S，B) 分析與解答：該題目主要考查棧的操作。 (1) 首先要實(shí)現(xiàn)運(yùn)算 Push_Stack(S，A)，其結(jié)果是將元素 A 壓入棧 S 中。若棧 S 滿，則出現(xiàn)上溢現(xiàn)象的處理；否則把元素 A 壓入棧頂，且元素 個(gè)數(shù)加 1。然后作 Pop_Stack(S)運(yùn)算， 將棧頂元素彈出，且元素個(gè)數(shù)減 1。 (2) 首先作 Pop_Stack(S)運(yùn)算。若棧 A 為空，則作下溢處理；否則彈 出棧頂元素。然后再進(jìn)行壓入運(yùn)算，將剛才彈出的元素壓入棧 S 中。 (3) 這種復(fù)合運(yùn)算復(fù)雜一些，在(1)、(2)的基礎(chǔ)上可知，這種運(yùn)算的 結(jié)果使棧 S 增加了一個(gè)棧頂元素 B。 3何謂隊(duì)列的上溢現(xiàn)象，一般有幾種解決方法，試簡(jiǎn)述之。 分析與解答：該題目主要考查隊(duì)列的存儲(chǔ)結(jié)構(gòu)。 在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)列指針為 front，隊(duì)尾指針為 rear， 隊(duì)列的容量(即存儲(chǔ)的空間大小)為 MAXSIZE。當(dāng)有元素要加入隊(duì)列(即入隊(duì)) 時(shí)，若 rear=MAXSIZE-1，則隊(duì)列已滿，此時(shí)就不能將該元素加入隊(duì)列。對(duì) 于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以 用循環(huán)隊(duì)列解決。 一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法： (1) 可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造 成空間使用率低，浪費(fèi)存儲(chǔ)空間，一般不采用這種方法。 (2) 采用移動(dòng)元素的方法，每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已 有的元素向?qū)︻^移動(dòng)一個(gè)位置，假定空余空間足夠。每當(dāng)刪去一個(gè)隊(duì)頭元 素，則可依次移動(dòng)隊(duì)列中的元素總是使 front 指針指向隊(duì)列中的第一個(gè)位 置。 (3) 采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán) 隊(duì)列，利用一維數(shù)組順序存儲(chǔ)并用取模運(yùn)算實(shí)現(xiàn)。 4設(shè)棧 S=1,2,3,4,5,6,7,其中 7 為棧頂元素。請(qǐng)寫(xiě)出調(diào)用 algo(&S)后 棧 S 的狀態(tài)。 void algo(PseqStack S) int x; PseqQueue Q； PseqStack T； Q=Init_SeqQueue( )； T=Init_SeqStack( )； while(!Empty_SeqStack(S) Pop_ SeqStack(S,&x); if (x/2!=0) Push_SeqStack(T，x)； else En_SeqQueue(Q，x)； while(!Empty_SeqQueue(Q) Out_ SeqQueue(Q,&x); Push_SeqStack(S，x)； while(!Empty_SeqStack(T) Pop_ SeqStack(T,&x); Push_SeqStack(S，x)； 分析與解答：本函數(shù)的功能是將順序棧 S 中遞增有序的整數(shù)中的所有偶數(shù) 調(diào)整到所有奇數(shù)之前，并且要求偶數(shù)按遞減序排列，奇數(shù)按遞增序排列。 算法首先設(shè)置并初始化中間棧 T 和中間隊(duì)列 Q， 然后將 S 棧中的整數(shù)出 棧，若整數(shù)為奇數(shù)，入棧 T,若為偶數(shù)，入隊(duì)列 Q。這樣 S=,T=7,5,3,1, 其中 1 為棧頂元素,Q=6,4,2,其中 6 為隊(duì)頭元素。然后，將 Q 中整數(shù)出隊(duì) 列并入棧 S, 這樣 S=6,4,2,其中 2 為棧頂元素,再將 T 中元素出棧，并入 棧 S, 這樣 S=6,4,2,1,3,5,7,其中 7 為棧頂元素。 最后 S 棧的狀態(tài)如圖 3.4 所示。 1 2 3 4 5 6 7 8 9 10 6 4 2 1 3 5 7 圖 3.4 調(diào)用 algo(&S)后棧 S 的狀態(tài) 5假設(shè)兩個(gè)隊(duì)列共享一個(gè)循環(huán)向量空間(如圖 3.5 所示)，其類(lèi)型 Queue2 定義如下： front1 rear1 rear0 front0 toptypedef struct DateType dataMAXSIZE; int front2,rear2; Queue2; 圖 3.5 雙循環(huán)隊(duì)列示意圖 對(duì)于i=0或1， fronti和reari分別為第i個(gè)隊(duì)列的頭指針和尾指針。 請(qǐng)對(duì)以下算法填空，實(shí)現(xiàn)第 i 個(gè)隊(duì)列的入隊(duì)操作。 int EnQueue (Queue2 *Q, int i, DateType x) /*若第 i 個(gè)隊(duì)列不滿，則元素 x 入隊(duì)列，并返回 1；否則返回 0*/ if(i1) return 0; if(Q-reari=Q-front (1) ) return 0; Q-data (2) =x; Q-reari=( (3) ); return 1; 分析與解答：入隊(duì)操作需先判隊(duì)滿。隊(duì)列是否滿，要看一個(gè)隊(duì)列的隊(duì)尾元 素位置與另一個(gè)隊(duì)列的隊(duì)首元素位置之間是否還有空間。我們規(guī)定，隊(duì)首 指針總是指向隊(duì)首元素的實(shí)際位置，隊(duì)尾指針總是指向隊(duì)尾元素的后一個(gè) 位置。 因此，0 號(hào)隊(duì)列隊(duì)滿的判斷條件是 rear0=front1。同樣，1 號(hào)隊(duì)列 隊(duì)滿的判斷條件是 rear1=front0。 這樣一來(lái)，就要判斷傳遞進(jìn)來(lái)的 i 是 0 還是 1。但程序中沒(méi)有提供判斷 i 的語(yǔ)句 。因此可以將上述隊(duì)滿的判斷條件統(tǒng)一成下列關(guān)系式： reari=front(i+1)%2。在上式中，當(dāng) i=0 時(shí)，(i+1)%2 為 1，當(dāng) i=1時(shí)，(i+1)%2 為 0。 上述程序，第 1 個(gè)空是判隊(duì)列 i 是否滿；第 2 個(gè)空是將 x 插入到隊(duì)列 i 的當(dāng)前隊(duì)尾， 即在 reari的位置上插入； 第 3 個(gè)空是修改隊(duì)列 i 的尾指針， 因?yàn)槭茄h(huán)隊(duì)列，所以要對(duì)向量的容量 MAXSIZE 取模。 本題答案是：(1) (i+1)%2 (或 1-i) (2) Q-reari (3) (Q-reari+1)% MAXSIZE 五算法設(shè)計(jì)題 1已知 Q 是一個(gè)非空隊(duì)列，S 是一個(gè)空棧。僅用隊(duì)列和棧的基本操作和少 量工作變量，編寫(xiě)一個(gè)算法，將隊(duì)列 Q 中的所有元素逆置。 分析：該題目主要考查隊(duì)列和棧的應(yīng)用。將隊(duì)列逆置的步驟為： (1)順序取出隊(duì)列中的元素，將其入棧； (2)所有元素入棧后，再?gòu)臈Ｖ兄饌€(gè)取出，入隊(duì)列。 算法描述如下： Reverse_queue(PseqQueue q) DataType x ; PSeqStack S ; S=Init_SeqStack( ); while(! Empty_SeqQueue(q) /*若隊(duì)列非空，則將隊(duì)列中的元素入 棧*/ Out_SeqQueue(q,&x); Push_SeqStack(S, x); while(!Empty_SeqStack(S) /*若棧非空，則將棧中元素入隊(duì)*/ Pop_SeqStack(S,&x); In_SeqQueue(q，x); 2試寫(xiě)一個(gè)算法，識(shí)別依次讀入的一個(gè)以為結(jié)束符的字符序列是否為形 如“序列 1&序列 2”模式的字符序列。其中序列 1 和序列 2 中都不含字符 & ，且序列 2 是序列 1 的逆序列。例如， “a+b&b+a”是屬該模式的字符 序列，而“1+3&3-1”則不是。 分析：本題主要利用棧的工作原理，對(duì)于給定的字符串在讀到字符&前 入棧，在逐個(gè)讀&之后的字符并和棧頂字符比較，若相等，則出棧，否 則序列 2 不是序列 1 的逆序列。 算法描述如下： int IsReverse( ) /*判斷輸入的字符串中&前和&后部分是否為逆串, 是則返回 1,否則返回 0*/ PSeqStack S; char e,ch; S=Init_SeqStack( ); while (e =getchar()!=&) /*將輸入的字符串中&的前半部分 入棧*/ Push_SeqStack (S,e)；; while (e=getchar()!=) /*遇到字符循環(huán)結(jié)束，否則進(jìn)行比 較*/ if (Empty_SeqStack(S) return 0; Pop_ SeqStack(S, &ch);if (e!=ch) return 0; if (!Empty_SeqStack(S) return 0; return 1; 3請(qǐng)利用兩個(gè)棧 s1 和 s2 來(lái)模擬一個(gè)隊(duì)列。用棧的運(yùn)算來(lái)實(shí)現(xiàn)該隊(duì)列的三 個(gè)運(yùn)算：inqueue，插入一個(gè)元素入隊(duì)列；outqueue，刪除一個(gè)元素出隊(duì)列； queue_empty，判斷隊(duì)列為空。 分析：由于隊(duì)列是先進(jìn)先出，而棧是后進(jìn)先出；所以只有經(jīng)過(guò)兩棧，即在 第一個(gè)棧里先進(jìn)后出，再經(jīng)過(guò)第二個(gè)棧后進(jìn)先出來(lái)實(shí)現(xiàn)隊(duì)列的先進(jìn)先出。 因此，用兩個(gè)棧模擬一個(gè)隊(duì)列運(yùn)算就是用一個(gè)棧作為輸入(輸入棧)，而另 一個(gè)棧作為輸出(輸出棧)。當(dāng)入隊(duì)列時(shí)，總是將數(shù)據(jù)進(jìn)入到輸入棧中。在 輸出時(shí)，如果輸出棧已空，則將輸入棧的所有數(shù)據(jù)壓入輸出棧中，然后由 輸出棧輸出數(shù)據(jù)；如果輸出棧不空，就從輸出棧輸出數(shù)據(jù)。顯然，只有在 輸入、輸出棧均空時(shí)隊(duì)列才為空。 一個(gè)棧 s1 作為輸入棧，用來(lái)插入數(shù)據(jù)，另一個(gè)棧 s2 作為輸出棧，用來(lái) 刪除數(shù)據(jù)，刪除數(shù)據(jù)時(shí)應(yīng)將前一棧 s1 中的 所有數(shù)據(jù)讀出，然后進(jìn)入到第 二個(gè)棧 s2 中。s1 和 s2 大小相同。 算法描述如下： void inqueue(SeqStack s1,int x) /*插入一個(gè)數(shù)據(jù)入隊(duì)列*/ if(s1-top=n) /*輸入棧 s1 已滿*/ if(Empty_SeqStack(s2) /*若輸出棧 s2 為空，則將 s1 中的所有 數(shù)據(jù)退棧后壓入 s2*/ while(!Empty_SeqStack(s2) Pop_SeqStack(s1, &x) ; Push_SeqStack(s2, x); else /*若輸出棧 s2 不為空，不能利用這里面的空間 存儲(chǔ)數(shù)據(jù)，隊(duì)列滿*/ printf(“隊(duì)列滿”); else /*輸入棧 s1 不滿，直接入棧*/ Push_SeqStack(s1,x); void outqueue(SeqStack s1,SeqStack s2,int x) /*刪除一個(gè)數(shù)據(jù) 出隊(duì)列*/ if (Empty_SeqStack(s1) & Empty_SeqStack(s2) /*隊(duì)列 空*/ printf(“隊(duì)列空”); else if (Empty_SeqStack(s2) /*s2 空*/ while(!Empty_SeqStack(s1) /*將 s1 的所有元素退棧 后壓入 s2*/ Pop_SeqStack(s1, &x) ; Push_SeqStack(s2,x); Pop_SeqStack(s2,&x); /*彈出棧 s2 的棧頂元素(隊(duì)首元素)并賦給 x*/ int queue_empty(SeqStack s1, SeqStack s2) /*判斷隊(duì)列為空*/ if (Empty_SeqStack(s1) & Empty_SeqStack(s2) return 1; /*隊(duì)列為空*/ else return 0; /*隊(duì)列不為空*/ 4. 用遞歸方法編程求 n 個(gè)元素的集合的冪集。n 為整數(shù)，集合包含的元素 為不大于 n 的正整數(shù)。 分析：考查集合 Sx(x=0，n-1，n)，和其冪集 P(Sx)，可以分析出它們 之間的關(guān)系如下。 S0=，P(S0)=； S1=1，P(S1)=,1；