【正文】 站序列，并請(qǐng)說明為什么不能得到或者如何得到（即寫出以 ‘S’表示進(jìn)棧和以 ‘X’表示出棧的棧操作序列）。解：(1) 123 231 321 213 132(2) 可以得到135426的出站序列，但不能得到435612的出站序列。因?yàn)?356出站說明12已經(jīng)在棧中，1不可能先于2出棧。 簡(jiǎn)述棧和線性表的差別。解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表?！尽?寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char）。void main(){Stack S。char x,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)。}解：stack【】 簡(jiǎn)述以下算法的功能（棧的元素類型SElemType為int）。(1) status algo1(Stack S){int i,n,A[255]。n=0。while(!StackEmpty(S)) { n++。 Pop(S,A[n])。 }for(i=1。i=n。i++) Push(S,A[i])。}(2) status algo2(Stack S,int e){Stack T。 int d。InitStack(T)。while(!StackEmpty(S)){Pop(S,d)。if(d!=e) Push(T,d)。}while(!StackEmpty(T)){Pop(T,d)。Push(S,d)。}}解：(1) 棧中的數(shù)據(jù)元素逆置 (2) 如果棧中存在元素e，將其從棧中清除 假設(shè)以S和X分別表示入棧和出棧的操作，則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對(duì)同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。解：任何前n個(gè)序列中S的個(gè)數(shù)一定大于X的個(gè)數(shù)。設(shè)兩個(gè)合法序列為：T1=S……X……S……T2=S……X……X……假定前n個(gè)操作都相同，從第n+1個(gè)操作開始，為序列不同的起始操作點(diǎn)。由于前n個(gè)操作相同，故此時(shí)兩個(gè)棧（不妨為棧A、B）的存儲(chǔ)情況完全相同，假設(shè)此時(shí)棧頂元素均為a。第n+1個(gè)操作不同，不妨T1的第n+1個(gè)操作為S，T2的第n+1個(gè)操作為X。T1為入棧操作，假設(shè)將b壓棧，則T1的輸出順序一定是先b后a；而T2將a退棧，則其輸出順序一定是先a后b。由于T1的輸出為……ba……，而T2的輸出順序?yàn)椤璦b……，說明兩個(gè)不同的合法棧操作序列的輸出元素的序列一定不同。 試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使。解：。因?yàn)檩斎胄蛄惺菑男〉酱笈帕械?，所以若，則可以理解為通過輸入序列可以得到輸出序列，顯然通過序列123是無法得到312的。所以不可能存在著ijk使。 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算(↑)優(yōu)先關(guān)系的慣例，畫出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程：ABC/D+E↑F解：BC=G G/D=H AH=I E^F=J I+J=K步驟OPTR棧OPND棧輸入字符主要操作1AB*C/D+E^FPUSH(OPND,A)2AB*C/D+E^FPUSH(OPTR,)3AB*C/D+E^FPUSH(OPND,B)4A B*C/D+E^FPUSH(OPTR,*)5*A BC/D+E^FPUSH(OPND,C)6*A B C/D+E^FOperate(B,*,C)7A G/D+E^FPUSH(OPTR,/)8/A GD+E^FPUSH(OPND,D)9/A G D+E^FOperate(G,/,D)10A H+E^FOperate(A,,H)11I+E^FPUSH(OPTR,+)12+IE^FPUSH(OPND,E)13+I E^FPUSH(OPTR,^)14+^I EFPUSH(OPND,F)15+^I E FOperate(E,^,F)16+I JOperate(I,+,J)17KRETURN 試推導(dǎo)求解n階梵塔問題至少要執(zhí)行的move操作的次數(shù)。解：【】 試將下列遞推過程改寫為遞歸過程。void ditui(int n){int i。i = n。while(i1)couti。}解：void ditui(int j){if(j1){coutj。ditui(j1)。}return。}【】 試將下列遞歸過程改寫為非遞歸過程。void test(int amp。sum){int x。cinx。if(x==0) sum=0。else{test(sum)。sum+=x。}coutsum。}解：void test(int amp。sum){Stack s。InitStack(s)。int x。do{cinx。Push(s,x)。}while(x0)。while(!StackEmpty(s)){Pop(s,x)。sum+=x。coutsumendl。}DestoryStack(s)。} 簡(jiǎn)述隊(duì)列和堆棧這兩種數(shù)據(jù)類型的相同點(diǎn)和差異處。解：棧是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。隊(duì)列也是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。 寫出以下程序段的輸出結(jié)果（隊(duì)列中的元素類型QElemType為char）。void main(){Queue Q。InitQueue(Q)。char x= ‘e’, y= ‘c’。EnQueue(Q, ‘h’)。EnQueue(Q, ‘r’)。EnQueue(Q, y)。DeQueue(Q, x)。EnQueue(Q, x)。DeQueue(Q, x)。EnQueue(Q, ‘a(chǎn)’)。While(!QueueEmpty(Q)){DeQueue(Q,y)。couty。}coutx。}解：char 簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類型均為int）。void algo3(Queue amp。Q){Stack S。int d。InitStack(S)。while(!QueueEmpty(Q)){DeQueue(Q, d)。Push(S, d)。}while(!StackEmpty(S)){Pop(S, d)。EnQueue(Q, d)。}}解：隊(duì)列逆置 若以1234作為雙端隊(duì)列的輸入序列，試分別求出滿足以下條件的輸出序列：(1) 能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列。(2) 能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出序列。(3) 既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列。 假設(shè)以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧，即在一維數(shù)組的存儲(chǔ)空間中存在著兩個(gè)棧，它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn)。試編寫實(shí)現(xiàn)這個(gè)雙向棧tws的三個(gè)操作：初始化inistack(tws)、入棧push(tws,i,x)和出棧pop(tws,i)的算法，其中i為0或1，用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧，并討論按過程(正/誤狀態(tài)變量可設(shè)為變參)或函數(shù)設(shè)計(jì)這些操作算法各有什么有缺點(diǎn)。解：class DStack{ElemType *top[2]。ElemType *p。int stacksize。int di。public:DStack(int m){p=new ElemType[m]。if(!p) exit(OVERFLOW)。top[0]=p+m/2。top[1]=top[0]。stacksize=m。}~DStack(){delete p。}void Push(int i,ElemType x){di=i。if(di==0){if(top[0]=p) *top[0]=x。else cerrStack overflow!。}else{if(top[1]p+stacksize1) *++top[1]=x。else cerrStack overflow!。}}ElemType Pop(int i){di=i。if(di==0){if(top[0]top[1]) return *++top[0]。else cerrStack empty!。}else{if(top[1]top[0]) return *top[1]。else cerrStack empty!。}return OK。}}。// 鏈棧的數(shù)據(jù)結(jié)構(gòu)及方法的定義typedef struct NodeType{ElemType data。NodeType *next。}NodeType,*LinkType。typedef struct{LinkType top。int size。}Stack。void InitStack(Stack amp。s){=NULL。=0。}void DestroyStack(Stack amp。s){LinkType p。while(){p=。=pnext。delete p。}}void ClearStack(Stack amp。s){LinkType p。while(){p=。=pnext。delete p。}}int StackLength(Stack s){return 。}Status StackEmpty(Stack s){if(==0) return TRUE。else return FALSE。}Status GetTop(Stack s,ElemType amp。e){if(!) return ERROR。else{e=data。return OK。}}Status Push(Stack amp。s,ElemType e){LinkType p。p=new NodeType。if(!p) exit(OVERFLOW)。pnext=。=p。pdata=e。++。return OK。}Status Pop(Stack amp。s,ElemType amp。e){LinkType p。if(){e=data。p=。=pnext。delete p。}return OK。}// 從棧頂?shù)綏５子肰isit()函數(shù)遍歷棧中每個(gè)數(shù)據(jù)元素void StackTraverse(Stack s,Status (*Visit)(ElemType e)){LinkType p。p=。while(p) Visit(pdata)。} （分別以H和S表示）等待調(diào)度，試編寫算法，輸出對(duì)這n節(jié)車廂進(jìn)行調(diào)度的操作（即入?；虺鰲２僮鳎┬蛄?，以使所有的軟席車廂都被調(diào)整到硬席車廂之前。解：int main(){Stack s。char Buffer[80]。int i=0,j=0。InitStack(s)。cout請(qǐng)輸入硬席(H)和軟席車廂(S)序列：。cinBuffer。coutBufferendl。while(Buffer[i]){if(Buffer[i]==39。S39。){Buffer[j]=Buffer[i]。j++。}else Push(s,Buffer[i])。i++。}while(Buffer[j]){Pop(s,Buffer[j])。j++。}coutBufferendl。return 0。} 試寫一個(gè)算法，識(shí)別一次讀入的一個(gè)以@為結(jié)束符的字符序列是否為形如‘序列1amp。序列2’模式的字符序列。其中序列1和序列2中都不含字符‘a(chǎn)mp?！倚蛄?是序列1的逆序列。例如，‘a(chǎn)+bamp。b+a’是屬該模式的字符序列，而‘1+3amp。31’則不是。解：BOOL Symmetry(char a[]){int i=0。Stack s。InitStack(s)。ElemType x。while(a[i]!=39。amp。39。 amp。amp。 a[i]){Push(s,a[i])。i++。}if(a[i]) return FALSE。