數(shù)據(jù)結(jié)構(gòu)第三章第四章

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

2、棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn).C. 兩個(gè)棧的棧頂在棧空間的某一位置相遇.D. 兩個(gè)棧均不空 , 且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底.3.一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第 i （ 1=i0) ? x* f(x-1):2); int i ;i =f(f(1);19. 表達(dá)式 a*(b+c)-d 的后綴表達(dá)式是 ( ) 。A abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd20*.表達(dá)式 3* 2(4+2*2-6*3)-5求值過程中當(dāng)掃描到6 時(shí)，對象棧和算符棧為（），其中 為乘冪 。A. 3,2,4,1,1；(*(+*-B. 3,2,8； (*-

3、C. 3,2,4,2,2；(*(-D. 3,2,8； (*(-21.設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D.棧22.用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（）。A. 僅修改頭指針B.僅修改尾指針C. 頭、尾指針都要修改D.頭、尾指針可能都要修改23.用不帶頭結(jié)點(diǎn)的單鏈表存儲隊(duì)列時(shí), 其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn), 其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。A僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C. 隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭 , 隊(duì)尾指針都可能要修改24.遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一

4、種稱為（）的數(shù)據(jù)結(jié)構(gòu)。A隊(duì)列B多維數(shù)組C棧D.線性表25.假設(shè)以數(shù)組 Am 存放循環(huán)隊(duì)列的元素, 其頭尾指針分別為 front和 rear ，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（）。A (rear-front+m)%mB rear-front+1C (front-rear+m)%mD(rear-front)%m26.循環(huán)隊(duì)列 A0.m-1 存放其元素值，用front和 rear 分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是( )。A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front27.循環(huán)隊(duì)列存儲在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（

5、）。A. rear=rear+1B. rear=(rear+1) % (m-1)C. rear=(rear+1) % mD. rear=(rear+1)%(m+1)28.若用一個(gè)大小為6 的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列， 且當(dāng)前 rear 和 front的值分別為0 和 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和 front的值分別為多少？ ()A.1 和5B. 2和 4C. 4和 2D. 5和 129.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（）位置。A鏈頭B鏈尾C鏈中D 任意30*.若以 1234 作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸

6、出序列是 ()。A. 1234B. 4132C. 4231D. 421331.最大容量為 n 的循環(huán)隊(duì)列，隊(duì)尾指針是rear ，隊(duì)頭是 front，則隊(duì)空的條件是（）。A. (rear+1) % n=frontB. rear=frontC rear+1=frontD. (rear-l) % n=front32.棧和隊(duì)列的共同點(diǎn)是（）。A. 都是先進(jìn)先出B.都是先進(jìn)后出C. 只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)33.棧的特點(diǎn)是 （）, 隊(duì)列的特點(diǎn)是 （）, 棧和隊(duì)列都是 （不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為 ,: A.先進(jìn)先出B.后進(jìn)先出C.進(jìn)優(yōu)于出: A.順

7、序存儲的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯Φ木€性結(jié)構(gòu)C. 限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)）。若進(jìn)棧序列為1,2,3,4則（D.出優(yōu)于進(jìn)1,2,3,4則（）是一個(gè)出隊(duì)列序列。 , : A. 3,2,1,4 B. 3,2,4,1C. 4,2,3,1D. 4,3,2,1F. 1,2,3,4G. 1,3,2,434.棧和隊(duì)都是（）A順序存儲的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu)C. 限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)35.設(shè)棧 S 和隊(duì)列 Q的初始狀態(tài)為空，元素e1，e2， e3，e4,e5和 e6 依次通過棧 S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若 6 個(gè)元素出隊(duì)的序列是e2， e4， e3,e

8、6,e5,e1則棧 S 的容量至少應(yīng)該是 ( ) 。A 6B. 4C. 3D. 236.設(shè)有編號為1， 2， 3， 4 的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺，下列不可能的出站順序?yàn)椋ǎ〢 1234B 1243C1324D142337.如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時(shí)（）A 必須判別棧是否滿B 必須判別棧是否為空C必須判別棧元素類型D隊(duì)?？刹蛔鋈魏闻袆e38.元素 A ， B， C，D 依次進(jìn)棧以后，棧頂元素是（）A AB BCCDD39.順序棧存儲空間的實(shí)現(xiàn)使用（）存儲棧元素。A 鏈表B 數(shù)組C循環(huán)鏈表D變量40.一個(gè)順序棧一旦說明，其占用空間的大?。ǎ〢 已固定B 可以變動C不能固定

9、D動態(tài)變化二判斷題1.消除遞歸不一定需要使用棧，（）2.棧是實(shí)現(xiàn)過程和函數(shù)等子程序所必需的結(jié)構(gòu)。（）3.兩個(gè)棧共用靜態(tài)存儲空間，對頭使用也存在空間溢出問題。（）4 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。（）5. 即使對不含相同元素的同一輸入序列進(jìn)行兩組不同的合法的入棧和出棧組合操作，所得的輸出序列也一定相同。6*.有 n 個(gè)數(shù)順序（依次）進(jìn)棧，出棧序列有Cn 種， Cn=1/ （ n+1） * （ 2n） !/(n!)*(n!)。（）7.棧與隊(duì)列是一種特殊操作的線性表。 （）8.若輸入序列為 1,2,3,4,5,6,則通過一個(gè)

10、?？梢暂敵鲂蛄?,2,5,6,4,1.（）9.棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。（）10若輸入序列為 1， 2， 3， 4， 5， 6，則通過一個(gè)?？梢暂敵鲂蛄?， 5， 4， 6， 2， 3。（）11.任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（）12.只有那種使用了局部變量的遞歸過程在轉(zhuǎn)換成非遞歸過程時(shí)才必須使用棧。（）13.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（）14.通常使用隊(duì)列來處理函數(shù)或過程的調(diào)用。（）15.隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。（）16.循環(huán)隊(duì)列通常用指針來實(shí)現(xiàn)隊(duì)列的頭尾相接。（）17.循環(huán)隊(duì)列也存在空間溢出問題。

11、 （）18.隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（ ）19.棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（）20.棧和隊(duì)列的存儲方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（?1. 空棧就是所有元素都為 0 的棧。22. 一個(gè)棧的輸入序列為： A ， B， C， D ，可以得到輸出序列： C，A ，B ， D。23. 隊(duì)列是限制在兩端進(jìn)行操作的線性表。24. 在循環(huán)隊(duì)列中，若尾指針 rear 大于頭指針 front ，其元素個(gè)數(shù)為 rear- front 。25. 隊(duì)列是一種“后進(jìn)先出”的線性表。三填空題1棧是 _的線性表，其運(yùn)算遵循_ 的原則。2 _是限定僅在表

12、尾進(jìn)行插入或刪除操作的線性表。3.一個(gè)棧的輸入序列是： 1， 2， 3 則不可能的棧輸出序列是 _。4.設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制) ，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_，而棧頂指針值是_H。設(shè)棧為順序棧，每個(gè)元素占 4 個(gè)字節(jié)。5.當(dāng)兩個(gè)棧共享一存儲區(qū)時(shí)，棧利用一維數(shù)組stack(1.n)top1為 _，棧 2 空時(shí)， top2為 _，棧滿時(shí)為表示，兩棧頂指針為_。top1與top2，則當(dāng)棧1 空時(shí)，6兩個(gè)棧共享空間時(shí)棧滿的條件_。7在作進(jìn)棧運(yùn)算時(shí)應(yīng)先判別棧是否_(1)_; 在作退棧運(yùn)算時(shí)

13、應(yīng)先判別棧是否_(2)_ ；當(dāng)棧中元素為n 個(gè)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為_(3)_ 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的_(4)_ 分別設(shè)在內(nèi)存空間的兩端，這樣只有當(dāng)_(5)_ 時(shí)才產(chǎn)生溢出。8. 多個(gè)棧共存時(shí)，最好用 _作為存儲結(jié)構(gòu)。9用 S 表示入棧操作，X 表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342 出棧順序，相應(yīng)的S 和 X 的操作串為 _。10.順序棧用data1.n存儲數(shù)據(jù)，棧頂指針是top, 則值為 x 的元素入棧的操作是_ 。11表達(dá)式23+(12*3-2)/4+34*5/7)+108/9的后

14、綴表達(dá)式是_。12. 循環(huán)隊(duì)列的引入，目的是為了克服_ 。13用下標(biāo) 0 開始的 N 元數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，為實(shí)現(xiàn)下標(biāo)變量M加 1 后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是： M= _14 _又稱作先進(jìn)先出表。15.隊(duì)列的特點(diǎn)是 _。16隊(duì)列是限制插入只能在表的一端，而刪除在表的另一端進(jìn)行的線性表，其特點(diǎn)是_。17*. 已知鏈隊(duì)列的頭尾指針分別是f 和 r ，則將值 x 入隊(duì)的操作序列是 _。18區(qū)分循環(huán)隊(duì)列的滿與空，只有兩種方法，它們是_和 _。19設(shè)循環(huán)隊(duì)列用數(shù)組 A1.M表示，隊(duì)首、隊(duì)尾指針分別是FRONT和 TAIL，判定隊(duì)滿的條件為 _。20*. 設(shè)循環(huán)隊(duì)列存放在向量sq.dat

15、a0:M中，則隊(duì)頭指針sq.front在循環(huán)意義下的出隊(duì)操作可表示為_，若用犧牲一個(gè)單元的辦法來區(qū)分隊(duì)滿和隊(duì)空（設(shè)隊(duì)尾指針sq.rear ）, 則隊(duì)滿的條件為 _ 。21表達(dá)式求值是 _應(yīng)用的一個(gè)典型例子。22循環(huán)隊(duì)列用數(shù)組 A0.m-1存放其元素值，已知其頭尾指針分別是front和 rear，則當(dāng)前隊(duì)列的元素個(gè)數(shù)是_ 。23設(shè) Q0.N-1 為循環(huán)隊(duì)列，其頭、尾指針分別為P 和 R，則隊(duì) Q中當(dāng)前所含元素個(gè)數(shù)為 _。24在棧中存取數(shù)據(jù)遵循的原則是：。25同一棧的各元素的類型。26在一個(gè)鏈?zhǔn)綏Ｖ校魲ｍ斨羔樀扔贜ULL ，則表示。27在隊(duì)列結(jié)構(gòu)中，允許插入的一端稱為，允許刪除的一端稱為。28隊(duì)

16、列在進(jìn)行出隊(duì)操作時(shí)，首先要判斷；入隊(duì)時(shí)首先要判斷。29設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)頭元素，尾指針rear 指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN ，則隊(duì)空的標(biāo)志為，隊(duì)滿的標(biāo)志為。四應(yīng)用題1.有 5 個(gè)元素，其入棧次序?yàn)椋篈， B， C，D， E，在各種可能的出棧次序中，以元素C， D 最先出棧（即 C 第一個(gè)且 D第二個(gè)出棧）的次序有哪幾個(gè)？2.如果輸入序列為 1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個(gè)序列:435612和 135426;請說明為什么不能或如何才能得到。 【 (3 分 ) 】3.若元素的進(jìn)棧序列為：A、 B、 C、 D、 E，運(yùn)用棧操作，能

17、否得到出棧序列B、C、A、E、D 和 D、B、A、C、 E？為什么？4.設(shè)輸入序列為 2， 3， 4，5， 6，利用一個(gè)棧能得到序列2， 5， 3， 4， 6 嗎？?？梢杂脝捂湵韺?shí)現(xiàn)嗎？（2 分）5*.試證明：若借助棧由輸入序列1,2, ,n 得到輸出序列為P1,P 2, ,P n（它是輸入序列的一個(gè)排列） ，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk, 使 P PP 。（ 15 分）jki6.設(shè)一數(shù)列的輸入順序?yàn)?23456，若采用堆棧結(jié)構(gòu)，并以A 和 D 分別表示入棧和出棧操作，試問通過入出棧操作的合法序列。（ 1） 能否得到輸出順序?yàn)?25641 的序列。（ 5 分）（ 2） 能否

18、得到輸出順序?yàn)?154623 的序列。（ 5 分）7.試推導(dǎo)出當(dāng)總盤數(shù)為 n 的 Hanoi塔的移動次數(shù)。【（5 分）】8.用一個(gè)數(shù)組 S（設(shè)大小為 MAX）作為兩個(gè)堆棧的共享空間。請說明共享方法，棧滿/ ?？盏呐袛鄺l件，并用C 設(shè)計(jì)公用的入棧操作 push（ i ， x），其中 i為 0 或 1，用于表示棧號， x 為入棧值。9. 給出循環(huán)隊(duì)列中元素個(gè)數(shù)的計(jì)算式( 設(shè)隊(duì)最大長度為 N, 隊(duì)首指針 FRONT，隊(duì)尾指針 REAR) (5 分 )10*. 計(jì)算算術(shù)表達(dá)式的值時(shí)，可用兩個(gè)棧作輔助工具。對于給出的一個(gè)表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧 S1 中，運(yùn)算符放入棧S2 中，但每

19、次掃描到運(yùn)算符時(shí)，要把它同S2的棧頂運(yùn)算符進(jìn)行優(yōu)先級比較，當(dāng)掃描到的運(yùn)算符的優(yōu)先級不高于棧頂運(yùn)算符的優(yōu)先級時(shí)，取出棧S1 的棧頂和次棧頂?shù)膬蓚€(gè)元素，以及棧S2 的棧頂運(yùn)算符進(jìn)行運(yùn)算將結(jié)果放入棧S1 中（得到的結(jié)果依次用T1、T2 等表示）。為方便比較，假設(shè)棧S2 的初始棧頂為?（?運(yùn)算符的優(yōu)先級低于加、減、乘、除中任何一種運(yùn)算）?，F(xiàn)假設(shè)要計(jì)算表達(dá)式：A-B*C/D+E/F 。寫出棧 S1 和 S2的變化過程?！荆?7 分）】11. 有字符串次序?yàn)?3*-y-a/y2,利用棧，給出將次序改為3y-*ay2/- 的操作步驟。（可用 X 代表掃描該字符串過程中順序取一個(gè)字符進(jìn)棧的操作，用 S代表從棧

20、中取出一個(gè)字符加入到新字符串尾的出棧操作。例如， ABC變?yōu)?BCA的操作步驟為 XXSXSS）【 ( 4分 ) 】12. 將兩個(gè)棧存入數(shù)組 V1.m 應(yīng)如何安排最好？這時(shí)?？?、棧滿的條件是什么？13.如果用一個(gè)循環(huán)數(shù)組q0.m-1表示隊(duì)列時(shí)，該隊(duì)列只有一個(gè)隊(duì)列頭指針front，不設(shè)隊(duì)列尾指針rear ，而改置計(jì)數(shù)器count 用以記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。（ 1）編寫實(shí)現(xiàn)隊(duì)列的三個(gè)基本運(yùn)算：判空、入隊(duì)、出隊(duì)（3 分）（ 2）隊(duì)列中能容納元素的最多個(gè)數(shù)是多少？（1 分）五 算法設(shè)計(jì)題1. 設(shè)有兩個(gè)棧 S1,S 2 都采用順序棧方式， 并且共享一個(gè)存儲區(qū) O.maxsize-1, 為了盡量利用空間，

21、 減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設(shè)計(jì)S1,S 2 有關(guān)入棧和出棧的操作算法。 （ 12 分）2.設(shè)從鍵盤輸入一整數(shù)的序列：a , a , a ， a , 試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)a -1 時(shí)，將123niai進(jìn)棧；當(dāng) ai =-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。（ 10分）3.設(shè)表達(dá)式以字符形式已存入數(shù)組En 中， #為表達(dá)式的結(jié)束符，試寫出判斷表達(dá)式中括號（和） ）是否配對的 C語言描述算法： EXYX(E); (注：算法中可調(diào)用棧操作的基本算法，假設(shè)棧容量足夠大。)（10 分）4.從鍵盤上輸入一個(gè)逆波蘭表達(dá)式，用

22、偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有 +、-、 *、/ 四種運(yùn)算。例如： 234 34+2*$( 注：算法中可調(diào)用棧操作的基本算法。) （10 分）5.假設(shè)以 I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空， 入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（ 1）下面所示的序列中哪些是合法的？A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO（ 2）通過對（ 1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返

23、回定被判定的操作序列已存入一維數(shù)組中） 。true，否則返回false（假6.設(shè)計(jì)一個(gè)算法，判斷一個(gè)算術(shù)表達(dá)式中的括號是否配對。算術(shù)表達(dá)式保存在帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)域： ch 和 link ，其中 ch 域?yàn)樽址愋汀?. 請利用兩個(gè)棧S1 和 S2 來模擬一個(gè)隊(duì)列。已知棧的三個(gè)運(yùn)算定義如下：PUSH(ST,x): 元素 x 入 ST 棧； POP(ST,x)：ST 棧頂元素出棧，賦給變量x；Sempty(ST) ：判 ST 棧是否為空。那么如何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：enqueue:插入一個(gè)元素入隊(duì)列；dequeue:刪除一個(gè)元素出隊(duì)列；queue_empty：

24、判隊(duì)列為空。 （請寫明算法的思想及必要的注釋）(10 分 )8. 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)，但不設(shè)頭指針，請寫出相應(yīng)的入隊(duì)列和出隊(duì)列算法。（ 10 分）9. 如果允許在循環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求：（ 1）寫出循環(huán)隊(duì)列的類型定義；（ 2）寫出 “從隊(duì)尾刪除 ”和“從隊(duì)頭插入 ”的算法。（ 12 分）10設(shè)計(jì)算法以求解從集合1.n 中選取 k（ kdata=x;s-next=r-next； r-next=s； r=s ；18 、犧牲一個(gè)存儲單元設(shè)標(biāo)記19、 TAILMOD M+1=FRONT20、 sq.front=(sq.front+1)%

25、(M+1)； return(sq.data(sq.front)； (sq.rear+1)%(M+1)=sq.front；21 、棧22、（ rear-front+m） % m；23、（ R-P+N） % N；24、后進(jìn)先出25 、必須一致26 、?？?7、隊(duì)尾隊(duì)頭28、隊(duì)列是否為空隊(duì)列是否為滿29、 front=rearfront=(rear+1)% MAXLEN四、應(yīng)用題1、三個(gè)： CDEBA， CDBEA， CDBAE2、輸入序列為 123456，不能得出435612，其理由是，輸出序列最后兩元素是12，前面 4 個(gè)元素（ 4356）得到后，棧中元素剩12，且 2 在棧頂，不可能棧底元素1

26、 在棧頂元素2 之前出棧。得到 135426 的過程如下： 1 入棧并出棧，得到部分輸出序列1；然后2 和 3 入棧， 3 出棧，部分輸出序列變?yōu)椋?3；接著 4 和 5 入棧， 5， 4 和 2 依次出棧，部分輸出序列變?yōu)?3542；最后 6 入棧并退棧，得最終結(jié)果135426。3、能得到出棧序列B、 C、 A、E、 D，不能得到出棧序列D、 B、 A、 C、 E。其理由為：若出棧序列以D 開頭，說明在 D 之前的入棧元素是A、B 和 C，三個(gè)元素中 C是棧頂元素， B 和 A 不可能早于 C出棧，故不可能得到D、B、A、C、 E 出棧序列。4、不能得到序列2， 5， 3，4， 6。?？梢杂?/p>

27、單鏈表實(shí)現(xiàn)，這就是鏈棧。由于棧只在棧頂操作，所以鏈棧通常不設(shè)頭結(jié)點(diǎn)。5、如果 i j ，則對于 pp的情況，則說明要將p 壓到 p 之上，ijijijji也就是在 p 出棧之后 p 才能出棧。這就說明，對于i j k，不可能出現(xiàn) pp pi的輸出序列。換句話說，對于輸入jijk序列 1， 2， 3，不可能出現(xiàn)3，1， 2 的輸出序列。6、（ 1）能得到 325641。在 123 依次進(jìn)棧后，3 和 2 出棧，得部分輸出序列32；然后 4， 5 入棧， 5出棧，得部分出棧序列 325；6 入棧并出棧，得部分輸出序列3256；最后退棧，直到棧空。得輸出序列325641。其操作序列為AAADDAAD

28、ADDD。（ 2）不能得到輸出順序?yàn)?54623 的序列。部分合法操作序列為ADAAAADDAD，得到部分輸出序列1546 后，棧中元素為23， 3 在棧頂，故不可能2 先出棧，得不到輸出序列 154623。7、設(shè) H n 為 n 個(gè)盤子的 Hanoi 塔的移動次數(shù)。 (假定 n 個(gè)盤子從鋼針X 移到鋼針 Z，可借助鋼針 Y)則 Hn=2H n-1+1 / 先將 n-1 個(gè)盤子從 X 移到 Y，第 n 個(gè)盤子移到 Z，再將那 n-1個(gè)移到 Z=2（ 2H+1）+1n-2=22 H n-2 +2+1=22（ 2Hn-3 +1） +2+1=23 H n-3 +22+2+1= 2k H n-k+2k

29、-1 +2k-2 + +21 +20n-1n-2n-310=2H 1+2+2 + +2 +2n-1n-210n因?yàn)?H 1=1，所以原式H n=2+2+ +2 +2 =2 -1n故總盤數(shù)為n 的 Hanoi 塔的移動次數(shù)是2 -1。8、兩棧共享一向量空間（一維數(shù)組） ，棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時(shí)為棧滿。設(shè)共享數(shù)組為SMAX，則一個(gè)棧頂指針為 -1，另一個(gè)棧頂指針為MAX時(shí)，棧為空。用 C 寫的入棧操作 push（ i， x）如下：const MAX= 共享?xiàng)？赡苓_(dá)到的最大容量typedefstructnodeelemtype sMAX；inttop2；anode；anode ds;int

30、 push( int i,elemtype x)/ds 為容量有 MAX個(gè)類型為 elemtype的元素的一維數(shù)組，由兩個(gè)棧共享其空間。i 的值為 0 或 1， x 為類型為 elemtype的元素。本算法將 x 壓入棧中。如壓棧成功，返回1；否則，返回 0。 if（ ds.top1-ds.top0=1） printf（“棧滿 n ”）； return （0）； switch （i ）case0： ds.s+ds.topi=x； break ；case1： ds.s-ds.topi=x；return（ 1）； / 入棧成功。9、循環(huán)隊(duì)列中元素個(gè)數(shù)為（ REAR-FRONT+N）%N。其中 FRONT是隊(duì)首指針，指向隊(duì)首元素的前一位置；REAR是隊(duì)尾指針，指向隊(duì)尾元素；N是隊(duì)列最大長度。10、步驟棧 S1棧 S2輸入的算術(shù)表達(dá)式（按字符讀入）初始?A- B*C/D+E/F?1A?A- B*C/D+E/F?2A?- B*C/D+E/F?3AB?-B*C/D+E/F?4AB?-* C/D+E/F?5ABC?-*C/D+E/F?6AT （注： T =B*C）?-/D+E/ F?117AT D?-/D+E/F?18AT2（注： T2=T1/D）?-+E/F?T3 （注： T3=A-T2）?+9T E?+E/F?310T E?+/ F?311T3EF?+/F?12