棧的一些習題

.棧和隊列具有相同的（）。人抽象數(shù)據(jù)類型 B.邏輯結構 C.存儲結構 D.運算.棧是（）。A.順序存儲的線性結構 B.鏈式存儲的非線性結構C.限制存取點的線性結構 D.限制存儲點的非線性結構.（）不是棧的基本操作。A.刪除棧頂元素 B.刪除棧底元素C.判斷棧是否為空 D.將棧置為空棧.假定利用數(shù)組a[n]順序存儲一個棧，用top表示棧頂指針，top==-1表示?？眨⒁阎獥Ｎ礉M，當元素x進棧時所執(zhí)行的操作為（）。A.a[--top]=xB.a[top--]=xC.a[++top]=xD.a[top++]=x.設有一個空棧，棧頂指針為1000H,每個元素需要1個存儲單元，在執(zhí)行Push、Push、Pop、Push、Pop、Push、Pop、Push操作后，棧頂指針的值為（）。A.1002HB.1003HC.1004HD.1005H.和順序棧相比，鏈棧有一個比較明顯的優(yōu)勢是（）。A.通常不會出現(xiàn)棧滿的情況 B.通常不會出現(xiàn)?？盏那闆r。插入操作更容易實現(xiàn) D.刪除操作更容易實現(xiàn).設鏈表不帶頭結點且所有操作均在表頭進行，則下列最不適合作為鏈棧的是()。A.只有表頭結點指針，沒有表尾指針的雙向循環(huán)鏈表.只有表尾結點指針，沒有表頭指針的雙向循環(huán)鏈表C.只有表頭結點指針，沒有表尾指針的單向循環(huán)鏈表D.只有表尾結點指針，沒有表頭指針的單向循環(huán)鏈表8.向一個棧頂指針為top的鏈棧中插入一個x結點，則執(zhí)行()。A.top->next=xB.x->next=top->next;top->next=xC.x->next=top;top=x D.x->next=top,top=top->next.鏈棧執(zhí)行Pop操作，并將出棧的元素存在x中應該執(zhí)行()。A.x=top;top=top->next B.x=top->dataC.top=top->next;x=top->data D.x=top->data;top=top->next.經過以下棧的操作后，變量x的值為()。InitStack(st);Push(st,a);Push(st,b);Pop(st,x);Top(st,x);A.aB.bC.NULLD.FALSE.3個不同元素依次進棧，能得到()種不同的出棧序列。A.4B.5C.6D.712.設a、b、c、d、e、f以所給的次序迸棧，若在進棧操作時，允許出棧操作，則下面得不到的序列為（）。A.fedcbaB.bcafedC.dcefbaD.cabdef13用S表示進棧操作，用X表示出棧操作，若元素的進棧順序是1234，為了得到1342的出棧順序，相應的S和X的操作序列為（）。A.SXSXSSXXB.SSSXXSXXC.SXSSXXSXD.SXSSXSXX14.【2010年計算機聯(lián)考真題】若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)3次進行退棧工作，則不可能得到的出棧序列是（）。A.dcebfaB.cbdaefC.bcaefdD.afedcb15.設找S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出棧的序列是e2、e4、e3、e6、e5、e1，則棧S的容量至少應該是（）。A.6B.4C.3D.216.【2009年計算機聯(lián)考真題】設棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q,且7個元素出隊的順序是bdefeag,則棧S的容量至少是（）。A.1B.2C.3D.4.若一個棧的輸入序列是1,2,3，…,n，輸出序列的第一個元素是n,則第i個輸出元素是（）。A.不確定B.n-iC.n-i-1D.n-i+1.一個棧的輸入序列為1,2,3，…,n輸出序列的第一個元素是i則第j個輸出元素是）。A,i-j-1B.i-jC.j-i+1D.不確定.某棧的輸入序列為a、b、c、d,下面的4個序列中，不可能是它的輸出序列的是（）。A.a,b,c,dB.c,b,d,aC.d,c,a,bD.a,c,b,d.若一個棧的輸入序列是P1,P2，…,Pn,其輸出序列是1,2,3，…,n,若P3=1,則p1的值（）。A.可能是2B.一定是2 C.不可能是2 D.不可能是3.若已知一個棧的入棧序列是1、2、3、4。其出棧序列為P1、P2、P3、P4,則P2、P4不可能是（）。A.2、4B,2、1C.4、3D.3、4.設棧的初始狀態(tài)為空，當字符序列"n1_"作為棧的輸入時，輸出長度為3，且可用做C語言標識符的序列有（）個。A.4B.5C.3D.623.【2011年計算機聯(lián)考真題】元素a、b、c、d、e依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數(shù)是（）。A.3B.4C.5D.624.采用共享棧的好處是（）。A.減少存取時間，降低發(fā)生上溢的可能B.節(jié)省存儲空間，降低發(fā)生上溢的可能C.減少存取時間，降低發(fā)生下溢的可能D.節(jié)省存儲空間，降低發(fā)生下溢的可能25.設有一個順序共享棧Share[0:11],其中第一個棧頂指針topi的初值為-1，第二個棧頂指針top2的初值為n，則判斷共享棧滿的條件是（）。A.top2-top1==1 B.top1-top2==1 C.top1==top2 D.以上都不對二,綜合應用題.有5個元素，其入棧次序為A、B、C、D、E,在各種可能的出棧次序中，第一個出棧元素為C且第二個出棧元素為D的出棧序列有哪幾個？.若元素的進棧序列為A、B、C、D、E,運用棧操作，能否得到出棧序列B、C、A、E、D和D、B、A、C、E?為什么？.假設以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，可以操作的序列稱為合法序列，否則稱為非法序列。1）下面所示的序列中哪些是合法的？a.IOIIOIOOb.IOOIOIIOc.IIIOIOIOd.IIIOOIOO2）通過對1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。4.設單鏈表的表頭指針為h，結點結構由data和next兩個域構成其中data域為字符型。試設計算法判斷該鏈表的前n個字符是否中心對稱。例如xyx、xyyx都是中心對稱。5.設有兩個棧s1、s2都采用順序棧方式，并且共享一個存儲區(qū)[0，…，maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向、迎面增長的存儲方式。試設計s1、s2有關入棧和出棧的操作算法。答案與解析一，單項選擇題B線性表、棧和隊列的邏輯結構都是相同的，都屬于線性結構，只是它們對數(shù)據(jù)的運算不同，從而表現(xiàn)出不同的特點。C首先棧是一種線性表，所以B、D錯。按存儲結構的不同可分為順序棧和鏈棧，但不可以把棧局限在某種存儲結構上，所以A錯。棧和隊列都是限制存取點的線性結構。B基本操作是指該結構最核心、最基本的運算，其他較復雜的操作可以通過基本操作實現(xiàn)。刪除棧底元素不屬于棧的基本運算，但它可以通過調用棧的基本運算求得。C入棧指針top加1，初始時top為-1，則第1個元素入找后，top為0，即指向棧頂元素，故入棧時應先將指針top加1，再將元素入棧，只有C符合題意。A每個元素需要1個存儲單元，所以每入棧一次top加1，出棧一次top減1。指針top的值依次為1001H，1002H,1001H,1002H，1001H，1002H，1001H，1002H。A順序棧采用數(shù)組存儲，數(shù)組的大小是固定的，不能動態(tài)地分配大小。和順序棧相比，鏈棧的最大優(yōu)勢在于它可以動態(tài)地分配存儲空間，所以答案為A。C通常棧的插入和刪除在表頭進行。對于選項C,插入和刪除一個結點后，仍需將其變?yōu)檠h(huán)單鏈表，因此需要找到其尾結點，時間復雜度為o（n）。若不做題干中的限制，則棧頂可取表頭（帶頭結點的鏈表）或第二個結點（不帶頭結點的鏈表），找指針的位置取頭結點（帶頭結點的鏈表）或表頭（不帶頭結點的鏈表。C鏈棧采用不帶頭結點的單鏈表表示時，進棧操作在首部插入一個結點x（即x->next=top）,插入完后需將top指向該插入的結點X。請思考當鏈棧存在頭結點時的情況。D這里假設棧頂指針指向的是棧頂元素，所以選D;而A中首先將top指針賦給了x，錯誤;B中沒有修改top指針的值；C為top指針指向棧頂元素的上一個元素時的答案。A執(zhí)行前3句后，棧st內的值為3,入其中5為棧頂元素，執(zhí)行第4句后，x的值為b，執(zhí)行最后一句后x的值為a。B對于n個不同元素進棧，出棧序列的個數(shù)為上述的公式叫做卡特蘭《合1合匕可數(shù)，可采用數(shù)學歸納法證明，有興趣的讀者可以參考組合數(shù)學的教材（知道該公式即可）。考題中給出的n值不會很大，可以根據(jù)棧的特點，若Xi已經出棧，則Xi前面的尚未出棧的元素一定逆置有序地出棧，因此可以采取例舉的方法。如a、b、c依次進棧的出棧序列有abc,acb,bac,bca,cba。D根據(jù)棧"先進后出”的特點，并且在進棧操作的同時允許出棧操作，顯然，答案D中c最先出棧，則此時棧內必定為a和b,但由于a先于b進棧，故要晚出棧。對于某個出棧的元素，在它之前進棧卻晚出棧的元素必定是按逆序出棧的，其余答案均是可能出現(xiàn)的情況。此題也可以采用將各序列逐個代入，以確定是否有對應的進出棧序列（類似下題）。D采用排除法，選項A、B、C得到的出棧序列分別為1243、3241、1324。由1234得到1342的進出棧序列為：1進，1出，2進，3進，3出，4進，4出，2出，故選D。D選項A可由a進，b進，c進，d進，d出，c出，e進，e出，b出，f進，f出，a出得到；選項B可由a進，b進，c進，c出，b出，d進，d出，a出，e進，e出，f進，f出得到；選項C可由a進，b進，b出，c進，c出，a出，d進，e進，e出，f進，f出，d出得到；選項D可由a進，a出，b進，c進，d進，e進，f進，f出，e出，d出，c出，b出得到，但要求不允許連續(xù)3次退棧操作，故選D。C本題將隊列和棧結合起來，由于隊列"先進先出"的特性，所以出隊的序列與進隊的序列是相同的，從而可以得到出棧的次序為e2、e4、e3、e6、e5、e1；再由棧"先進后出”的特性，進棧的次序為e1、e2、e3、e4、e5、e6,可見，排在某個元素之后出棧卻排在它之前進棧的元素個數(shù)，表示之前棧內的元素個數(shù)。因此，e4進棧后，e1和e3在棧中；而后e4和e3出找；e6進找后，e5和e1也在找中。因此，找的最小容量為3。找內的最大深度為3，故棧S的容量至少是3。另解：由于元素的出隊順序和入隊順序是一樣的，所以，元素的出棧順序也就是b、d、c、f、e、a、g,所以，元素的入棧出棧順序為Push(S,a)，Push(S,b)，Pop(S,b)，Push(S,c)，Push(S,d)，Pop(S,d)，Pop(S,c)，Push(S,e)。Push(S,f)，Pop(S,f)，Pop(S，e),Pop(S，a)，Push(S,g)，Pop(S,g)。假設初始所需容量為0，每做一次Push操作進行一次加1操作，每做一次Pop進行一次減1操作，記錄容量的最大值為3，所以答案選C。D第n個元素先出棧，說明前n-1個元素都已經按順序入棧，由“先進后出”的特點可知，此時的輸出序列一定是輸入序列的逆序，故答案選D。D當?shù)趇個元素第一個出棧時，則i之前的元素可以依次排在i之后出棧，但剩余的元素可以在此時進棧并且也會排在i之前的元素出棧，所以，第j個出棧的元素是不確定的。C對于A，可能的順序是a入，合出，5入小出，c入，c出，d入，d出。對于B，可能的順序是a入小入一入一出，b出，d入，d出，a出。對于D，可能的順序是合入評出，5入一入〃出，b出，d入，d出。C沒有對應的序列。另解：若出棧序列的第一個元素為d，則出棧序列只能是dcba。該思想通常也適用了出棧序列的局部分析：如12345入棧，問出棧序列34152是否正確？如何分析？若第一個出棧元素是3,則此時12必停留在棧中，它們出棧的相對順序只能是21，故34152錯誤。C入棧序列是P1，P2，…，Pn。由于P3=1，即P1、P2、P3連續(xù)入棧后，第一個出棧元素是P3，說明P1、P2已經按序進棧，根據(jù)先進后出的特點可知，P2必定在P1之前出棧，而第二個出棧元素是2,而此時P1必定不是棧頂元素，因為P2尚未出棧。因此P1的值不可能是2。C對于A，可能的順序是1入棧，1出棧，2入棧，2出棧，3入棧，3出棧，4入棧，4出棧。對于B，可能的順序是1入棧，2入棧，3入棧，3出找，2出找，4入棧，4出橈，1出棧。對于D,可能的順序是1入棧，1出棧，2入棧，3入棧，3出棧，2出棧，4入棧，4出棧。C則沒有對應的序列。C標識符的第一個字符必須是大小寫英文字母或者下畫線，而不能是數(shù)字。按照上述規(guī)定"n1二，三個字符符合規(guī)定的標識符有n1_、n_1、_1n,_n1四種形式。第一種：n進棧再出棧，1進棧再出棧，_進棧再出棧。第二種：n進棧再出棧，1進棧，_進棧，_出棧，1出棧。第三種：n進棧，1進棧_進棧，_出棧，1出棧，n出棧。而根據(jù)棧的操作特性，_n1這種情況不可能出現(xiàn)，故選C。B出棧順序必為d_c_b_a，e的順序不定，在任意一個"_"上都有可能。另解：d首先出棧，則abc停留在棧中，此時錢的狀態(tài)如下圖所示。此時可以有如下4種操作：①e進棧后出棧，則出棧序列為decba;②c出棧，e進棧后出棧，出棧序列為dceba;③cb出棧，e進棧后出棧，出棧序列為dcbea;④cba出找，e進棧后出棧，出棧序列為dcbae。第23題圖B存取棧中的元素都只需要0(1)的時間，所以，減少存取時間無從談起。另外，棧的插入和刪除操作都是在棧頂進行的，只可能發(fā)生上溢(棧頂指針超出了最大范圍)不可能發(fā)生下溢（對于上溢、下溢，只需大概了解即可，不必深究），因此本題答案為B。A這種情況就是前面我們所描述的詳細內容請參見本節(jié)考點精析部分對共享棧的講解。另外，讀者可以思考若top1的初值為0，top2的初值為n-1時棧滿的條件。注意：棧頂、隊頭與隊尾的指針的定義是不唯一的，讀者務必要仔細審題。二■綜合應用題.解答：CD出棧后的狀態(tài)如下圖所示。此時有如下3種操作：①E進棧后出棧，則出棧序列為CDEBA；②B出棧，E進棧后出棧，出棧序列為CDBEA；③B出棧，A出棧，E進棧后出棧，出棧序列為CDBAE。所以，以CD開頭的出棧序列有：CDEBA、CDBEA、CDBAE三種。第1題圖.解答：能得到出棧序列BCAED?？捎葾進，B進，B出，C進，C出，A出，D進，E進，E出，D出得到。不能得到出棧序列DBACE。若出棧序列以D開頭，說明在D之前的入棧元素是A、B和C，三個元素中C是棧頂元素，B和A不可能早于C出棧，故不可能得到出棧序列DBACE。.解答：A、D合法，而B、C不合法。在B中，先入棧1次，再連續(xù)出棧2次，錯誤。在C中，入棧和出棧次數(shù)不一致，會導致最終的棧不空。A、D均為合法序列，請自行模擬。注意：在操作過程中，入棧次數(shù)一定大于或等于出棧次數(shù)；結束時，棧一定為空。2）設被判定的操作序列已存入一維數(shù)組人中。算法的基本設計思想：依次逐一掃描入棧出棧序列（即由T和"O"組成的字符串），每掃描至任一位置均需檢查出棧次數(shù)（即"O"的個數(shù)）是否小于入棧次數(shù)（7的個數(shù)），若大于則為非法序列。掃描結束后，再判斷入棧和出棧次數(shù)是否相等，若不相等則不合題意，為非法序列。intJudge（charA[]）{〃判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true,否則返回falsei=0;j=k=0;//i為下標"和k分別為字母I和O的個數(shù)5.while(A[i]!='\0'){//未到字符數(shù)組尾switch(A[i]){case'I';j++;break;//入棧次數(shù)增1case'O':k++;10.if(k>j){printf("序列非法\n");exit(0);)11.}i++;//不論A[i]是T或“0”，指針i均后移.}//while.15.if(j!=k){.printf("序列非法\n");.returnfalse;.}else{.printf("序列合法\n");.returntrue;.}.}另解：入棧后，棧內元素個數(shù)加1；出棧后，棧內元素個數(shù)減1，因此，可以將判定一組出入棧序列是否合法，轉化為一組+1、-1組成的序列，它的任意前綴子序列的累加和不小于0(每次出?；蛉霔２僮骱笈袛?，則合法；否則，非法。4.解答：算法思想：使用棧來判斷鏈表中的數(shù)據(jù)是否中心對稱。將鏈表的前一半元素依次進棧。在處理鏈表的后一半元素時，當訪問到鏈表的一個元素后，就從棧中彈出一個元素，兩個元素比較，若相等，則將鏈表中下一個元素與棧中再彈出的元素比較，直至鏈表到尾。這時若棧是空棧，則得出鏈表中心對稱的結論；否則，當鏈表中的一個元素與棧中彈出元素不等時，結論為鏈表非中心對稱，結束算法的執(zhí)行。intdc(LinkListL,intn){//h是帶頭結點的n個元素單鏈表，本算法判斷鏈表是否是中心對稱chars[n/2];inti=1;//i記結點個數(shù)，s字符棧P=L->next;//p是鏈表的工作指針，指向待處理的當前元素for{i=0;i<n/2;i++){//鏈表前一半元素進棧s[i]=p->data;p=p->next;)i--;〃恢復最后的i值if(n%2==1)//若n是奇數(shù)，后移過中心結點.p=p->next;..while(p!=NULL&&s[i]==p->data){//檢測是否中心對稱14.i--;//i充當找頂指針15.p=p->next;16.)if(i==-1)//棧為空找return1;〃鏈表中心對稱elsereturn0;〃鏈表不中心對稱)算法先將"鏈表的前一半"元素(字符)進棧。當n為偶數(shù)時，前一半和后一半的個數(shù)相同；當n為奇數(shù)時，鏈表中心結點字符不必比較，移動鏈表指針到下一字符開始比較。比較過程中遇到不相等時，立即退出while循環(huán)，不再進行比較。本題也可以先將單鏈表中的元素全部入棧，然后再次掃描單鏈表L并比較，直到比較到單鏈表L尾為止，但是算法需要兩次掃描單鏈表L,效率不及上述算法高。5.解答：兩個棧共享向量空間，將兩個棧的棧底設在向量兩端，初始時，s1棧頂指針為-1,s2棧頂指針為maxsize。兩個棧頂指針相鄰時為棧滿。兩個棧頂相向、迎面增長，棧頂指針指向棧頂元素。