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

1、第3章 棧與隊(duì)列一、單項(xiàng)選擇題1元素A、C、D依次進(jìn)順序棧后，棧頂元素是 ，棧底元素是 。AA BBCCDD2經(jīng)過以下棧運(yùn)算后，x的值是 。InitStack(s)；Push(s,a)；Push(s,b)；Pop(s,x)；GetTop(s,x);AaBbC1D03已知一個(gè)棧的進(jìn)棧序列是ABC，出棧序列為CBA，經(jīng)過的棧操作是 。Apush,pop,push,pop,push,popBpush,push,push,pop,pop,popCpush,push,pop,pop,push,popDpush,pop,push,push,pop,pop4設(shè)一個(gè)棧的輸入序列為A、B、C、D，則借助一個(gè)棧所

2、得到的序列是 。AA,B,C,DBD,C,B,ACA,C,D,B DD,A,B,C5一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 。Aedcba Bdecba CdceabDabcde6已知一個(gè)棧的進(jìn)棧序列是1，2，3，,n，其輸出序列的第一個(gè)元素是i，則第j個(gè)出棧元素是 。Ai Bn-iCj-i+1D不確定7已知一個(gè)棧的進(jìn)棧序列是1，2，3，n，其輸出序列是p1,p2,Pn，若p1=n，則pi的值 。AiBn-iCn-i+1D不確定8設(shè)n個(gè)元素進(jìn)棧序列是1，2，3，n，其輸出序列是p1,p2,pn，若p1=3,則p2的值 。A一定是2B一定是1C不可能是1D以上都不對9設(shè)n

3、個(gè)元素進(jìn)棧序列是p1,p2,pn，其輸出序列是1，2，3，n，若p3=1,則p1的值 。A可能是2B一定是1C不可能是2D不可能是310設(shè)n個(gè)元素進(jìn)棧序列是p1,p2,pn，其輸出序列是1，2，3，n，若p3=3,則p1的值 。A可能是2B一定是2C不可能是1D一定是111設(shè)n個(gè)元素進(jìn)棧序列是p1,p2,pn，其輸出序列是1，2，3，n，若pn=1,則pi(1in-1)的值 。An-i+1 Bn-iCiD有多種可能12判定一個(gè)順序棧S為空的條件為 。AS.top= =S.baseBS.top!= S.baseCS.top!= S.base+S.stacksizeDS.top= = S.base

4、+S.stacksize 13判定一個(gè)順序棧S為棧滿的條件是 。AS.top-S.base= =S.stacksizeBS.top= = S.baseCS.top-S.base!=S.stacksizeDS.top!= S.base14鏈棧與順序棧相比有一個(gè)明顯的優(yōu)點(diǎn)，即 。A插入操作方便 B通常不會出現(xiàn)棧滿的情況C不會出現(xiàn)?？盏那闆rD刪除操作更加方便15最不適合用作鏈棧的鏈表是 。A只有表頭指針沒有表尾指針的循環(huán)雙鏈表B只有表尾指針沒有表頭指針的循環(huán)雙鏈表C只有表尾指針沒有表頭指針的循環(huán)單鏈表D只有表頭指針沒有表尾指針的循環(huán)單鏈表16如果以鏈表作為棧的存儲結(jié)構(gòu)，則退鏈棧操作時(shí) 。A必須判別鏈

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

6、S ->data; S = S ->next;19經(jīng)過以下隊(duì)列運(yùn)算后，隊(duì)頭的元素是 。InitQueue(qu);enQueue(qu,a);enQueue(qu,b);enQueue(qu,c);deQueue(qu);Aa BbC1 D020經(jīng)過以下隊(duì)列的運(yùn)算后，QueueEmpty(q) 的值是 。InitQueue(qu);enQueue(qu,a);enQueue(qu,b);deQueue(qu,x);deQueue(qu,y);Aa BbC1 D021元素A,B,C,D順序連續(xù)進(jìn)入隊(duì)列qu后，隊(duì)頭元素是 ，隊(duì)尾元素是 。AA BBCC DD22一個(gè)隊(duì)列的入隊(duì)序列為1,

7、2,3,4，則隊(duì)列可能的輸出序列是_.A4,3,2,1B1,2,3,4C1,4,3,2 D3,2,4,1二、填空題1棧是一種具有 特性的線性表。2順序棧和鏈棧的區(qū)別僅在于 不同。3如果棧的最大長度難以估計(jì)，則最好使用 。4一個(gè)棧的輸入序列是1,2,3,4,5，則棧的輸出序列1,2,3,4,5是 。5若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈棧S，則創(chuàng)建一個(gè)空棧所要執(zhí)行的操作是 。6對于鏈棧S，進(jìn)棧操作在 端進(jìn)行，出棧操作在 端進(jìn)行。7隊(duì)列是一種具有 特性的線性表。8順序隊(duì)列和鏈隊(duì)列的區(qū)別僅在于 的不同。9如果隊(duì)列的最大長度難以估計(jì)，則最好使用_。三、判斷題1順序棧中元素值的大小是有序的。2在n個(gè)元素進(jìn)棧后

8、，它們的出棧順序和進(jìn)棧順序一定正好相反。3棧頂元素和棧底元素有可能是同一個(gè)元素。4若用S1m表示順序棧的存儲空間，則對棧的進(jìn)棧，出棧操作最多只能進(jìn)行m次。5棧是一種對進(jìn)棧，出棧操作總次數(shù)作了限制的線性表。6空棧沒有棧頂指針。7棧和隊(duì)列都是限制存取端的線性表。8隊(duì)列是一種對進(jìn)隊(duì)列，出隊(duì)列操作的次序作了限制的線性表。9n個(gè)元素進(jìn)隊(duì)列的順序和出隊(duì)列的順序總是一致的。10順序隊(duì)中有多少元素，可以根據(jù)隊(duì)首指針的值和隊(duì)尾指針的值來計(jì)算。11若用“隊(duì)頭指針的值和隊(duì)尾指針的值相等”作為環(huán)形順序隊(duì)為空的標(biāo)志，則在設(shè)置一個(gè)空隊(duì)列時(shí)，只需給隊(duì)頭指針和隊(duì)尾指針賦同一個(gè)值，不管什么值都可以。12無論是順序隊(duì)列，還是鏈隊(duì)

9、列，入隊(duì)和出隊(duì)操作的時(shí)間復(fù)雜度都是O(1)。13隊(duì)列的輸入序列為1,2,3,n，輸出序列為a1,a2,an, 則ai<ai+1(1in-1) 四、簡答題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á)輸出序列，當(dāng)所有元素均到達(dá)輸出序列后，有哪些序列可以作為高級語言的變量名？3設(shè)有一個(gè)數(shù)列的輸入順序?yàn)?,2,3,4,5,6，若采用棧結(jié)構(gòu)，并以A和D分別表示進(jìn)棧和出棧操作，試問通過進(jìn)棧和出棧操作的合法序列是什么？（1）能否得到輸

10、出順序?yàn)?,2,5,6,4,1的序列。（2）能否得到輸出順序?yàn)?,5,4,6,2,3的序列。4簡述線性表、棧和隊(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è)棧的共享空間。請說明共享方法，棧滿和?？盏呐袛鄺l件，并用C/C+語言設(shè)計(jì)公用的初始化棧運(yùn)算InitStack1(st)、判?？者\(yùn)算StackEmpty1(st,i)、入棧運(yùn)算Push(st,i,x)和出棧運(yùn)算Pop(st,i,x)，其中i為1或2，用于