數(shù)據(jù)結(jié)構(gòu)棧與隊列習(xí)題

1、v1.0可編輯可修改第3章棧與隊列一、單項選擇題1 元素A E、C D依次進順序棧后，棧頂元素是,棧底元素是A. AB. BC. CD. D2. 經(jīng)過以下棧運算后，x的值是。InitStack(s) ; Push(s,a) ; Push(s,b) ; Pop(s,x) ； GetTop(s,x);A. aB.bC.1D.03. 已知一個棧的進棧序列是 ABC出棧序列為CBA經(jīng)過的棧操作是。A. push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,pus

2、h,pop,pop4. 設(shè)一個棧的輸入序列為 A、B、C D,A. A,B,C,DC. A,C,D,B5. 一個棧的進棧序列是a, b, c, d, e,A. edcbaC. dceab6. 已知一個棧的進棧序列是1, 2, 3,則第j個出棧元素是。A. iC. j-i+17. 已知一個棧的進棧序列是1, 2, 3,若p1= n,貝卩pi的值。A. iM 昔助一個棧所得到的序列是。B. D,C,B,AD. D,A,B,C則棧的不可能的輸出序列是。B. decbaD. abcde,n，其輸出序列的第一個元素是i ,B. n-iD.不確定,n,其輸出序列是p1,p2,Pn,B. n-i7C. n-

3、i+1D.不確定8設(shè)n個元素進棧序列是1,2,3,，n,其輸出序列是pi,p2,pn,若pi=3, 則P2的值。A. 定是2B.定是1C不可能是1D.以上都不對9. 設(shè)n個元素進棧序列是Pi,p 2,pn,其輸出序列是1, 2, 3, ,n,若p3=1,則3的值。A.可能是2B.定是1C不可能是2D.不可能是310. 設(shè)n個兀素進棧序列是p1,p2,p n,其輸出序列是1, 2, 3, ,n,若p3=3,貝卩p1的值。A.可能是2B.定是2C不可能是1D. 定是111. 設(shè)n個兀素進棧序列是p1,p2,p n,其輸出序列是1, 2, 3, ,n,若pn=1,貝U pi(1 <i <

4、n-1)的值。n-iA. n-i+1C. iD.有多種可能12.判定一個順序棧S為空的條件為A.=B. !=C. != +D. = = +13. 判定一個順序棧S為棧滿的條件是A.=B. =C. D.!=14. 鏈棧與順序棧相比有一個明顯的優(yōu)點，即 。A.插入操作方便B通常不會出現(xiàn)棧滿的情況C. 不會出現(xiàn)棧空的情況D.刪除操作更加方便15. 最不適合用作鏈棧的鏈表是 。A.只有表頭指針沒有表尾指針的循環(huán)雙鏈表B. 只有表尾指針沒有表頭指針的循環(huán)雙鏈表C. 只有表尾指針沒有表頭指針的循環(huán)單鏈表D. 只有表頭指針沒有表尾指針的循環(huán)單鏈表16. 如果以鏈表作為棧的存儲結(jié)構(gòu)，則退鏈棧操作時 A.必須判

5、別鏈棧是否滿C.必須判別鏈棧是否空17.向一個不帶頭結(jié)點的棧頂指針為行。A=s；C. s->next=1st;1st=s;B. 判別鏈棧元素的類型D. 對鏈棧不作任何判別1st的鏈棧中插入一個s所指結(jié)點時，則執(zhí)1st- >n ext=s;B. s->next=1st->next;1st->nextD. s->next=1st;1st->next;18. 從一個不帶頭結(jié)點的棧頂指針為 S的鏈棧中刪除一個結(jié)點時，用x保存被刪除結(jié)點的值，則執(zhí)行。A. x=S; S = S ->next;B. x= S ->data;C. S = S ->n

6、ext;x= S ->data;D. x= S ->data; S = S ->next;19. 經(jīng)過以下隊列運算后，隊頭的元素是 。In itQueue(qu);e nQueue(qu,a);e nQueue(qu,b);e nQueue(qu,c);deQueue(qu );B. bA. aC. 1D. 020. 經(jīng)過以下隊列的運算后，QueueEmpty(q)的值是。In itQueue(qu);e nQueue(qu,a);e nQueue(qu,b);deQueue(qu,x);deQueue(qu,y);A. aB. bC. 1D. 021. 元素A,B,C,D順

7、序連續(xù)進入隊列qu后，隊頭元素是，隊尾元素B. BA. AC. CD. D22. 一個隊列的入隊序列為1,2,3,4，貝U隊列可能的輸出序列是 A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,1二、填空題1 .棧是一種具有 特性的線性表。2. 順序棧和鏈棧的區(qū)別僅在于 不同。3. 如果棧的最大長度難以估計，則最好使用 。4. 一個棧的輸入序列是1,2,3,4,5 ，則棧的輸出序列1,2,3,4,5 是5. 若用不帶頭結(jié)點的單鏈表來表示鏈棧S,則創(chuàng)建一個空棧所要執(zhí)行的操作6. 對于鏈棧S,進棧操作在端進行，出棧操作在 端進行7. 隊列是一種具有特性的線性表。8. 順

8、序隊列和鏈隊列的區(qū)別僅在于 的不同。9. 如果隊列的最大長度難以估計，則最好使用 。三、判斷題1. 順序棧中元素值的大小是有序的。2. 在n個元素進棧后，它們的出棧順序和進棧順序一定正好相反。3. 棧頂元素和棧底元素有可能是同一個元素。4. 若用S1m表示順序棧的存儲空間，則對棧的進棧，出棧操作最多只能進行m次。5. 棧是一種對進棧，出棧操作總次數(shù)作了限制的線性表。6. 空棧沒有棧頂指針。7. 棧和隊列都是限制存取端的線性表。v1.0可編輯可修改8隊列是一種對進隊列，出隊列操作的次序作了限制的線性表。9. n個元素進隊列的順序和出隊列的順序總是一致的。10順序隊中有多少元素，可以根據(jù)隊首指針的

9、值和隊尾指針的值來計算。11.若用“隊頭指針的值和隊尾指針的值相等”作為環(huán)形順序隊為空的標(biāo)志，則在設(shè)置一個空隊列時，只需給隊頭指針和隊尾指針賦同一個值，不管什么值 都可以。12無論是順序隊列，還是鏈隊列，入隊和出隊操作的時間復(fù)雜度都是0(1)。13 .隊列的輸入序列為1,2,3,n ，輸出序列為a1,a2,an,則 ai<ai+1 (1 w i Wn-1)四、簡答題1有5個元素，其進棧次序為A,B,C,D,E,在各種可能的出棧次序中，以元素C,D 最先出棧(即C第一個且D第二個出棧)的次序有哪幾個2設(shè)輸入元素為1, 2, 3, P和A,入棧次序為1,2,3,P,A，元素經(jīng)過棧后到達 輸出

10、序列，當(dāng)所有元素均到達輸出序列后，有哪些序列可以作為高級語言的 變量名3設(shè)有一個數(shù)列的輸入順序為1,2,3,4,5,6 ，若采用棧結(jié)構(gòu)，并以A和D分別 表示進棧和出棧操作，試問通過進棧和出棧操作的合法序列是什么(1) 能否得到輸出順序為3,2,5,6,4,1的序列。(2) 能否得到輸出順序為1,5,4,6,2,3的序列。4 簡述線性表、棧和隊列的異同。5.設(shè)棧S和隊列Q的初始狀態(tài)都為空，元素a,b,c,d,e 和f依次通過棧S， 個元素出棧后即進入隊列Q,若6個元素的出隊的序列是b,d,c,f,e,a ，則棧 S的容量至少應(yīng)該存多少個元素。五、算法設(shè)計題1 .用一個一維數(shù)組S (設(shè)大小為MaxSize)作為兩個棧的共享空間。請說明共享 方法，棧滿和?？盏呐袛鄺l件，并用C/C+語言設(shè)計公用的初始化棧運算5v1.0可編輯可修改InitStackl(st) 、判?？者\算 StackEmpty1(st,i)、入棧運算 Push(st,i,x)和出棧運算Pop(st,i,x)，其中i為1或2,用于表示棧好