棧和隊列答案

《棧和隊列答案》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、3.1若按教科書3.1.1節(jié)中圖3.1(b)所示鐵道進行車廂調(diào)度（注意：兩側鐵道均為單向行駛道），則請回答：(1)如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？(2)如果進站的車廂序列為123456，則能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到（即寫出以‘S’表示進棧和以‘X’表示出棧的棧操作序列）。解：(1)123231321213132(2)可以得到135426的出站序列，但不能得到435612的出站序列。因為4356出站說明12已經(jīng)在棧中，1不可能先于2出棧。3.2簡述棧和線性表的差別。解：線性表是

2、具有相同特性的數(shù)據(jù)元素的一個有限序列。棧是限定僅在表尾進行插入或刪除操作的線性表。3.3寫出下列程序段的輸出結果（棧的元素類型SElemType為char）。voidmain(){StackS;charx,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Push(S,‘a(chǎn)’);Push(S,y);Pop(S,x);Push(S,‘t’);Push(S,x);Pop(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);}printf(x);}解：stack3.4簡述以下

3、算法的功能（棧的元素類型SElemType為int）。(1)statusalgo1(StackS){inti,n,A[255];n=0;while(!StackEmpty(S)){n++;Pop(S,A[n]);}for(i=1;i<=n;i++)Push(S,A[i]);}(2)statusalgo2(StackS,inte){StackT;intd;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}while(!StackEmpty(T)){Pop(T,d);Push(S,d)

4、;}}解：(1)棧中的數(shù)據(jù)元素逆置(2)如果棧中存在元素e，將其從棧中清除3.5假設以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準則，并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體，而不是值）序列。解：任何前n個序列中S的個數(shù)一定大于X的個數(shù)。設兩個合法序列為：T1=S……X……S……T2=S……X……X……假定前n個

5、操作都相同，從第n+1個操作開始，為序列不同的起始操作點。由于前n個操作相同，故此時兩個棧（不妨為棧A、B）的存儲情況完全相同，假設此時棧頂元素均為a。第n+1個操作不同，不妨T1的第n+1個操作為S，T2的第n+1個操作為X。T1為入棧操作，假設將b壓棧，則T1的輸出順序一定是先b后a；而T2將a退棧，則其輸出順序一定是先a后b。由于T1的輸出為……ba……，而T2的輸出順序為……ab……，說明兩個不同的合法棧操作序列的輸出元素的序列一定不同。3.6試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序列的一個排列)，則在輸出序列中不可能出現(xiàn)這樣

6、的情形：存在著i

7、B*C/D+E^F#PUSH(OPTR,-)3#-AB*C/D+E^F#PUSH(OPND,B)4#-AB*C/D+E^F#PUSH(OPTR,*)5#-*ABC/D+E^F#PUSH(OPND,C)6#-*ABC/D+E^F#Operate(B,*,C)7#-AG/D+E^F#PUSH(OPTR,/)8#-/AGD+E^F#PUSH(OPND,D)9#-/AGD+E^F#Operate(G,/,D)10#-AH+E^F#Operate(A,-,H)11#I+E^F#PUSH(OPTR,+)12#+IE^F#PUSH(OPND,E)13#+IE^F#PUS

8、H(OPTR,^)14#+^IEF#PUSH(OPND,F)15#