【文章內(nèi)容簡(jiǎn)介】 快速度將兩表合并成一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表。 3．在帶頭結(jié)點(diǎn)的單鏈表上，給出求表長(zhǎng) Length(L)的算法，并加入簡(jiǎn)要的注釋或說(shuō)明。 4．設(shè)單鏈表具有頭結(jié)點(diǎn)， 且表中元素各不相同，試給出在單鏈表中查找值為 x的結(jié)點(diǎn)的算法，并加入簡(jiǎn)要的注釋或說(shuō)明。 5．設(shè)單鏈表具有頭結(jié)點(diǎn)，且表中元素各不相同，試給出在單鏈表中刪除值為 x的結(jié)點(diǎn)的算法。 第三章 棧和隊(duì)列 一、 選擇題 1. 對(duì)于棧操作數(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)先判別棧是否( ② )。當(dāng)棧中元素為 n 個(gè) ,作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢 ,則說(shuō)明該棧的最大容量為( ③ )。 為了增加內(nèi)存空間的利用率和減少溢出的可能性 ,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí) ,應(yīng)將兩棧的 ( ④ )分別設(shè)在這片內(nèi)存空間的兩端 ,這樣 ,當(dāng) ( ⑤ )時(shí)，才產(chǎn)生上溢。 ① , ② : A. 空 B. 滿 C. 上溢 D. 下溢 ③ : A. n1 B. n C. n+1 D. n/2 12 ④ : A. 長(zhǎng)度 B. 深度 C. 棧頂 D. 棧底 ⑤ : A. 兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn) . B. 其中一個(gè)棧的棧頂?shù)竭_(dá)棧空間的中心點(diǎn) . C. 兩個(gè)棧的棧頂在?？臻g的某一位置相遇 . D. 兩個(gè)棧均不空 ,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底 . 3. 一個(gè)棧的輸入序列為 123?n ，若輸出序列的第一個(gè)元素是 n，輸出第 i（ 1=i=n）個(gè)元素是（ ）。 A. 不確定 B. ni+1 C. i D. ni 4. 若一個(gè)棧的輸入序列為 1,2,3,?,n ，輸出序列的第一個(gè)元素是 i，則第 j 個(gè)輸出元素是（ ）。 A. ij1 B. ij C. ji+1 D. 不確定的 5. 若已知一個(gè)棧的入棧序列是 1,2,3,?,n ，其輸出序列為 p1,p2,p3， ? ， pN,若 pN是n，則 pi是 ( )。 A. i B. ni C. ni+1 D. 不確定 6. 有六個(gè)元素 6， 5， 4， 3， 2， 1 的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（ ） 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 6 7. 設(shè)棧的輸入序列是 1， 2， 3， 4,則（ ）不可能是其出棧序列。 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，則下列序列中不可能是棧的輸出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 設(shè)一個(gè)棧的輸入序列是 1， 2， 3， 4， 5,則下列序列中，是棧的合法輸出序列的是（ ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆棧的輸入序列為 a, b， c ， d,下面的四個(gè)序列中，不可能是它的輸出序列的是（ ）。 A. a， c， b， d B. b, c， d， a C. c, d， b, a D. d, c， a， b 11. 設(shè) abcdef以所給的次序進(jìn)棧，若在進(jìn)棧操作時(shí)，允許退棧操作 ,則下面得不到的序列為（ ）。 A． fedcba B. bcafed C. dcefba D. cabdef 12. 設(shè)有三個(gè)元素 X， Y， Z 順序進(jìn)棧（進(jìn)的過(guò)程中允許出棧），下列得不到的出棧排列是 ( )。 13 A． XYZ B. YZX C. ZXY D. ZYX 13. 輸入序列為 ABC，可以變?yōu)?CBA時(shí)，經(jīng)過(guò)的棧操作為（ ） 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,pop 14. 若一個(gè)棧以向量 V[1..n]存儲(chǔ)，初始棧頂指針 top 為 n+1，則下面 x 進(jìn)棧的正確操作是 ( )。 A． top:=top+1。 V [top]:=x B. V [top]:=x。 top:=top+1 C. top:=top1。 V [top]:=x D. V [top]:=x。 top:=top1 15. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間 V[1..m]， top[i]代表第 i個(gè)棧 ( i =1,2)棧頂，棧 1的底在 v[1]，棧 2的底在 V[m]，則棧滿的條件是（ ）。 A. |top[2]top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 棧在（ ）中應(yīng)用。 A. 遞歸調(diào)用 B. 子程序調(diào)用 C. 表達(dá)式求值 D. A，Ｂ，Ｃ 17. 一個(gè)遞歸算法必須包括（ ）。 A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 18. 執(zhí)行完下列語(yǔ)句段后， i值為：（ ） int f(int x) { return ((x0) ? x* f(x1):2)。} int i 。 i =f(f(1))。 A． 2 B. 4 C. 8 D. 無(wú)限遞歸 19. 表達(dá)式 a*(b+c)d 的后綴表達(dá)式是 ( )。 A． abcd*+ B. abc+*d C. abc*+d D. +*abcd 20. 表達(dá)式 3* 2^(4+2*26*3)5求值過(guò)程中當(dāng)掃描到 6時(shí)，對(duì)象棧和算符棧為（ ），其中 ^為乘冪 。 A. 3,2,4,1,1； (*^(+* B. 3,2,8； (*^ C. 3,2,4,2,2； (*^( D. 3,2,8； (*^( 21. 設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧 22. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)（ ）。 14 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 23. 用不帶頭結(jié) 點(diǎn)的單鏈表存儲(chǔ)隊(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. 遞歸過(guò)程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。 A． 隊(duì)列 B． 多維數(shù)組 C． 棧 D. 線性表 25. 假設(shè)以數(shù)組 A[m]存放循環(huán)隊(duì)列的元素 ,其頭尾指針?lè)謩e為 front和 rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。 A． (rearfront+m)%m B． rearfront+1 C． (frontrear+m)%m D． (rearfront)%m 26. 循環(huán)隊(duì)列 A[0..m1]存放其元素值，用 front 和 rear 分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是 ( )。 A. (rearfront+m)%m B. rearfront+1 C. rearfront1 D. rearfront 27. 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組 A[0..m]中，則入隊(duì)時(shí)的操作為（ ）。 A. rear=rear+1 B. rear=(rear+1) mod (m1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 28. 若用一個(gè)大小為 6 的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear 和 front 的值分別為 0和 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后， rear和 front的值分別為多少？ ( ) A. 1和 5 B. 2和 4 C. 4和 2 D. 5和 1 29. 已知輸入序列為 abcd 經(jīng)過(guò)輸出受限的雙向隊(duì)列后能得到的輸出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不對(duì) 30. 若以 1234 作為雙端隊(duì)列的輸入序列，則既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是 ( )。 A. 1234 B. 4132 C. 4231 D. 4213 31. 最大容量為 n 的循環(huán)隊(duì)列，隊(duì)尾指針是 rear，隊(duì)頭是 front，則隊(duì) 空的條件是 （ ）。 15 A. (rear+1) MOD n=front B. rear=front C． rear+1=front D. (rearl) MOD n=front 32. 棧和隊(duì)列的共同點(diǎn)是（ ）。 A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn) 33. 棧的特點(diǎn)是（ ① ） ,隊(duì)列的特點(diǎn)是（ ② ） ,棧和隊(duì)列都是（ ③ ）。若進(jìn)棧序列為 1,2,3,4 則（ ④ ）不可能是一個(gè)出棧序列（不一定全部進(jìn)棧后再出棧）；若進(jìn)隊(duì)列的序列為 1,2,3,4 則（ ⑤ ）是一個(gè)出隊(duì)列序列。 ① , ② : A. 先進(jìn)先出 B. 后進(jìn)先出 C. 進(jìn)優(yōu)于出 D. 出優(yōu)于進(jìn) ③ : ④ , ⑤ : A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4 34. 棧和隊(duì)都是（ ） A．順序存儲(chǔ)的線性結(jié)構(gòu) B. 鏈?zhǔn)酱鎯?chǔ)的非線性結(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依次通過(guò)棧 S，一個(gè)元素出棧后即進(jìn)隊(duì)列 Q，若 6個(gè)元素出隊(duì)的序列是 e2， e4， e3,e6,e5,e1則棧 S的容量至少應(yīng)該是 ( )。 A． 6 B. 4 C. 3 D. 2 36. 用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的（ ）位置。 A． 鏈頭 B． 鏈尾 C． 鏈中 37. 依次讀入數(shù)據(jù)元素序列 {a， b， c， d， e， f， g}進(jìn)棧 ,每進(jìn)一個(gè)元素，機(jī)器可要求下一個(gè)元素進(jìn)?；驈棗?，如此進(jìn)行，則?？諘r(shí)彈出的元素構(gòu)成的序列是以下哪些序列？ A． {d ， e， c， f， b， g， a} B. {f， e， g， d， a， c， b} C. {e， f， d， g， b， c， a}