棧和隊(duì)列練習(xí)題

1、選擇題：1、設(shè)abcdef 以所給的次序進(jìn)棧，假設(shè)在進(jìn)棧操作時(shí)，允許退棧操作,那么下面得不到的序列為 D 。 Afedcba B. bcafed C. dcefba D. cabdef 2、假設(shè)一個(gè)棧的入棧序列是 1,2,3,n，其輸出序列為 p1,p2,p3，pN,假設(shè)pN 是 n，那么 pi 是( D )。 A. i B. n-i C. n-i+1 D. 不確定3、設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用 D 數(shù)據(jù)結(jié)構(gòu)最正確。 A線性表的順序存儲結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧4、用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí) D 。 A. 僅修改頭指針 B.

2、僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改5、遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為 C 的數(shù)據(jù)結(jié)構(gòu)。 A隊(duì)列 B多維數(shù)組 C棧 D. 線性表6、假設(shè)以數(shù)組 Am存放循環(huán)隊(duì)列的元素,其頭尾指針分別為 front 和rear，那么當(dāng)前隊(duì)列中的元素個(gè)數(shù)為 A 。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m 7、假設(shè)用一個(gè)大小為 6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和 front 的值分別為 0和 3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再參加兩個(gè)元素后，rear 和 front

3、的值分別為多少？( B )A. 1 和 5 B. 2 和4 C. 4 和2 D. 5 和1 8、最大容量為 n 的循環(huán)隊(duì)列，隊(duì)尾指針是 rear，隊(duì)頭是 front，那么隊(duì)空的條件是 A 。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front 9、棧和隊(duì)列的共同點(diǎn)是 C 。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn) 10、設(shè)棧S和隊(duì)列 Q 的初始狀態(tài)為空，元素 e1，e2，e3，e4,e5 和e6 依次通過棧 S，一個(gè)元素出棧后即進(jìn)隊(duì)列 Q，假設(shè)

4、 6 個(gè)元素出隊(duì)的序列是 e2，e4，e3,e6,e5,e1 那么棧 S 的容量至少應(yīng)該是( C )。 A 6 B. 4 C. 3 D. 2 判斷題：棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)。 消除遞歸不一定需要使用棧，此說法 任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出時(shí)機(jī)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 名詞解釋：棧隊(duì)列循環(huán)隊(duì)列1什么是遞歸程序？ 2遞歸程序的優(yōu)、缺點(diǎn)是什么？ 3 遞歸程序在執(zhí)行時(shí)，應(yīng)借助于什么來完成？ 4 遞歸程序的入口語句、出口語句一般用什么語句實(shí)現(xiàn)？算法題：1、數(shù)組a，有n個(gè)元素，用遞歸實(shí)現(xiàn)以下算法：求和，求

5、最大值，求平均數(shù)。判斷是否為一個(gè)遞增數(shù)組。大那么繼續(xù)，否那么返回false結(jié)束：2、試將以下遞歸過程改寫為非遞歸過程。 void test(int *sum) int x； scanf(“%d, &x)； if(x = 0) *sum=0 else test(sum); *sum+=x; printf("%d ",*sum)； 3、請利用兩個(gè)棧 S1 和 S2 來模擬一個(gè)隊(duì)列。棧的三個(gè)運(yùn)算定義如下：PUSH(ST , x):元素 x 入 ST 棧；POP(ST , &x)：ST 棧頂元素出棧，賦給變量 x；Sempty(ST)：判斷 ST 棧是否為空。那么如

6、何利用棧的運(yùn)算來實(shí)現(xiàn)該隊(duì)列的三個(gè)運(yùn)算：enqueue:插入一個(gè)元素入隊(duì)列；dequeue:刪除一個(gè)元素出隊(duì)列；queue_empty:判斷隊(duì)列為空。請寫明算法的思想及必要的注釋，不需要代碼實(shí)現(xiàn) 題目分析棧的特點(diǎn)是后進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)先出。所以，用兩個(gè)棧s1和s2模擬一個(gè)隊(duì)列時(shí)，s1作輸入棧，逐個(gè)元素壓棧，以此模擬隊(duì)列元素的入隊(duì)。當(dāng)需要出隊(duì)時(shí)，將棧s1退棧并逐個(gè)壓入棧s2中，s1中最先入棧的元素，在s2中處于棧頂。s2退棧，相當(dāng)于隊(duì)列的出隊(duì)，實(shí)現(xiàn)了先進(jìn)先出。顯然，只有棧s2為空且s1也為空，才算是隊(duì)列空。算法討論算法中假定棧s1和棧s2容量相同。出隊(duì)從棧s2出，當(dāng)s2為空時(shí)，假設(shè)s1不空，

7、那么將s1倒入s2再出棧。元素從棧s1倒入s2，必須在s2空的情況下才能進(jìn)行，即在要求出隊(duì)操作時(shí)，假設(shè)s2空，那么不管s1元素多少只要不空，就要全部倒入s2中。入隊(duì)在s1，當(dāng)s1滿后，假設(shè)s2空，那么將s1倒入s2，之后再入隊(duì)。因此隊(duì)列的容量為兩棧容量之和。(1) int enqueue(stack s1,elemtp x)/s1是容量為n的棧，棧中元素類型是elemtp。本算法將x入棧，假設(shè)入棧成功返回1，否那么返回0。if(top1=n && !Sempty(s2) /top1是棧s1的棧頂指針，是全局變量。printf(“棧滿);return(0); /s1滿s2非空,這

8、時(shí)s1不能再入棧。if(top1=n && Sempty(s2) /假設(shè)s2為空，先將s1退棧,元素再壓棧到s2。 while(!Sempty(s1) POP(s1,x);PUSH(s2,x); PUSH(s1,x); return(1); /x入棧，實(shí)現(xiàn)了隊(duì)列元素的入隊(duì)。(2) void dequeue(stack s2,s1)/s2是輸出棧，本算法將s2棧頂元素退棧，實(shí)現(xiàn)隊(duì)列元素的出隊(duì)。if(!Sempty(s2) /棧s2不空，那么直接出隊(duì)。 POP(s2,x); printf(“出隊(duì)元素為,x); else /處理s2空棧。 if(Sempty(s1) printf(“

9、隊(duì)列空);exit(0);/假設(shè)輸入棧也為空，那么判定隊(duì)空。 else /先將棧s1倒入s2中，再作出隊(duì)操作。 while(!Sempty(s1) POP(s1,x);PUSH(s2,x); POP(s2,x); /s2退棧相當(dāng)隊(duì)列出隊(duì)。 printf(“出隊(duì)元素，x); /結(jié)束算法dequue。(3) int queue_empty()/本算法判用棧s1和s2模擬的隊(duì)列是否為空。if(Sempty(s1)&&Sempty(s2) return(1);/隊(duì)列空。 else return(0); /隊(duì)列不空。 D D D D CA B A C CT T T T1、棧是只準(zhǔn)在一端進(jìn)

10、行插入和刪除操作的線性表，允許插入和刪除的一端叫棧頂，另一端叫棧底。最后插入的元素最先刪除，故棧也稱后進(jìn)先出LIFO表。2、隊(duì)列是允許在一端插入而在另一端刪除的線性表，允許插入的一端叫隊(duì)尾，允許刪除的一端叫隊(duì)頭。最先插入隊(duì)的元素最先離開刪除，故隊(duì)列也常稱先進(jìn)先出FIFO表。3、用常規(guī)意義下順序存儲結(jié)構(gòu)的一維數(shù)組表示隊(duì)列，由于隊(duì)列的性質(zhì)隊(duì)尾插入和隊(duì)頭刪除，容易造成“假溢出現(xiàn)象，即隊(duì)尾已到達(dá)一維數(shù)組的上下標(biāo)，不能再插入，然而隊(duì)中元素個(gè)數(shù)小于隊(duì)列的長度容量。循環(huán)隊(duì)列是解決“假溢出的一種方法。通常把一維數(shù)組看成首尾相接。在循環(huán)隊(duì)列下，通常采用“犧牲一個(gè)存儲單元或“作標(biāo)記的方法解決“隊(duì)滿和“隊(duì)空的判定問題。1一個(gè)函數(shù)在結(jié)束本函數(shù)之前，直接或間接調(diào)用函數(shù)自身，稱為遞歸。例如，函數(shù)f在執(zhí)行中，又調(diào)用函數(shù)f自身，這稱為直接遞歸；假設(shè)函數(shù)f在執(zhí)行中，調(diào)用函數(shù)g，而g在執(zhí)行中，又調(diào)用函數(shù)f，這稱為間接遞歸。在實(shí)際應(yīng)用中，多為直接遞歸，也常簡稱為遞歸。2遞歸程序的優(yōu)點(diǎn)是程序結(jié)構(gòu)簡單、清晰