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

1、v1.0可編輯可修改第3章棧與隊(duì)列一、單項(xiàng)選擇題1 元素A E、C D依次進(jìn)順序棧后，棧頂元素是,棧底元素是A. AB. BC. CD. D2. 經(jīng)過以下棧運(yùn)算后，x的值是。InitStack(s) ; Push(s,a) ; Push(s,b) ; Pop(s,x) ； GetTop(s,x);A. aB.bC.1D.03. 已知一個(gè)棧的進(jìn)棧序列是 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è)一個(gè)棧的輸入序列為 A、B、C D,A. A,B,C,DC. A,C,D,B5. 一個(gè)棧的進(jìn)棧序列是a, b, c, d, e,A. edcbaC. dceab6. 已知一個(gè)棧的進(jìn)棧序列是1, 2, 3,則第j個(gè)出棧元素是。A. iC. j-i+17. 已知一個(gè)棧的進(jìn)棧序列是1, 2, 3,若p1= n,貝卩pi的值。A. iM 昔助一個(gè)棧所得到的序列是。B. D,C,B,AD. D,A,B,C則棧的不可能的輸出序列是。B. decbaD. abcde,n，其輸出序列的第一個(gè)元素是i ,B. n-iD.不確定,n,其輸出序列是p1,p2,Pn,B. n-i7C. n-

3、i+1D.不確定8設(shè)n個(gè)元素進(jìn)棧序列是1,2,3,，n,其輸出序列是pi,p2,pn,若pi=3, 則P2的值。A. 定是2B.定是1C不可能是1D.以上都不對(duì)9. 設(shè)n個(gè)元素進(jìn)棧序列是Pi,p 2,pn,其輸出序列是1, 2, 3, ,n,若p3=1,則3的值。A.可能是2B.定是1C不可能是2D.不可能是310. 設(shè)n個(gè)兀素進(jìn)棧序列是p1,p2,p n,其輸出序列是1, 2, 3, ,n,若p3=3,貝卩p1的值。A.可能是2B.定是2C不可能是1D. 定是111. 設(shè)n個(gè)兀素進(jì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.判定一個(gè)順序棧S為空的條件為A.=B. !=C. != +D. = = +13. 判定一個(gè)順序棧S為棧滿的條件是A.=B. =C. D.!=14. 鏈棧與順序棧相比有一個(gè)明顯的優(yōu)點(diǎn)，即 。A.插入操作方便B通常不會(huì)出現(xiàn)棧滿的情況C. 不會(huì)出現(xiàn)棧空的情況D.刪除操作更加方便15. 最不適合用作鏈棧的鏈表是 。A.只有表頭指針沒有表尾指針的循環(huán)雙鏈表B. 只有表尾指針沒有表頭指針的循環(huán)雙鏈表C. 只有表尾指針沒有表頭指針的循環(huán)單鏈表D. 只有表頭指針沒有表尾指針的循環(huán)單鏈表16. 如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退鏈棧操作時(shí) A.必須判

5、別鏈棧是否滿C.必須判別鏈棧是否空17.向一個(gè)不帶頭結(jié)點(diǎn)的棧頂指針為行。A=s；C. s->next=1st;1st=s;B. 判別鏈棧元素的類型D. 對(duì)鏈棧不作任何判別1st的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)1st- >n ext=s;B. s->next=1st->next;1st->nextD. s->next=1st;1st->next;18. 從一個(gè)不帶頭結(jié)點(diǎn)的棧頂指針為 S的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除結(jié)點(diǎn)的值，則執(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)過以下隊(duì)列運(yùn)算后，隊(duì)頭的元素是 。In itQueue(qu);e nQueue(qu,a);e nQueue(qu,b);e nQueue(qu,c);deQueue(qu );B. bA. aC. 1D. 020. 經(jīng)過以下隊(duì)列的運(yùn)算后，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ù)進(jìn)入隊(duì)列qu后，隊(duì)頭元素是，隊(duì)尾元素B. BA. AC. CD. D22. 一個(gè)隊(duì)列的入隊(duì)序列為1,2,3,4，貝U隊(duì)列可能的輸出序列是 A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D. 3,2,4,1二、填空題1 .棧是一種具有 特性的線性表。2. 順序棧和鏈棧的區(qū)別僅在于 不同。3. 如果棧的最大長(zhǎng)度難以估計(jì)，則最好使用 。4. 一個(gè)棧的輸入序列是1,2,3,4,5 ，則棧的輸出序列1,2,3,4,5 是5. 若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈棧S,則創(chuàng)建一個(gè)空棧所要執(zhí)行的操作6. 對(duì)于鏈棧S,進(jìn)棧操作在端進(jìn)行，出棧操作在 端進(jìn)行7. 隊(duì)列是一種具有特性的線性表。8. 順

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

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

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