【正文】 typedef struct{ PolyTerm *data。 int last。} SqPoly。// 建立一個(gè)多項(xiàng)式Status PolyInit(SqPoly amp。L){ int i。 PolyTerm *p。 cout請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù):。 cin。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。 if(!) return ERROR。 p=。 for(i=0。i。i++){ cout請(qǐng)輸入系數(shù):。 cinpcoef。 cout請(qǐng)輸入指數(shù):。 cinpexp。 p++。 } return OK。} // 求多項(xiàng)式的值double PolySum(SqPoly amp。L,double x0){ double Pn,x。 int i,j。 PolyTerm *p。 p=。 for(i=0,Pn=0。i。i++,p++){ for(j=0,x=1。jpexp。j++) x=x*x0。 Pn=Pn+pcoef*x。 } return Pn。} ，編寫(xiě)求的算法，將結(jié)果多項(xiàng)式存放在新辟的空間中，并分析你的算法的時(shí)間復(fù)雜度。解：// 求兩多項(xiàng)式的差Status PolyMinus(SqPoly amp。L,SqPoly amp。L1,SqPoly amp。L2){ PolyTerm *p,*p1,*p2。 p=。 p1=。 p2=。 int i=0,j=0,k=0。 while(iamp。amp。j){ if(p1expp2exp){ pcoef=p1coef。 pexp=p1exp。 p++。 k++。 p1++。 i++。 } else if(p1expp2exp){ pcoef=p2coef。 pexp=p2exp。 p++。 k++。 p2++。 j++。 } else{ if(p1coef!=p2coef){ pcoef=(p1coef)(p2coef)。 pexp=p1exp。 p++。 k++。 } p1++。 p2++。 i++。 j++。 } } if(i) while(i){ pcoef=p1coef。 pexp=p1exp。 p++。 k++。 p1++。 i++。 } if(j) while(j){ pcoef=p2coef。 pexp=p2exp。 p++。 k++。 p2++。 j++。 } =k。 return OK。}，稀疏多項(xiàng)式采用的循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)LinkedPoly定義為typedef struct PolyNode { PolyTerm data。 struct PolyNode *next。} PolyNode, *PolyLink。typedef PolyLink LinkedPoly。 試以循環(huán)鏈表作稀疏多項(xiàng)式的存儲(chǔ)結(jié)構(gòu)，編寫(xiě)求其導(dǎo)函數(shù)的方法，要求利用原多項(xiàng)式中的結(jié)點(diǎn)空間存放其導(dǎo)函數(shù)多項(xiàng)式，同時(shí)釋放所有無(wú)用結(jié)點(diǎn)。解：Status PolyDifferential(LinkedPoly amp。L){ LinkedPoly p,q,pt。 q=L。 p=Lnext。 while(p!=L){ if(p==0){ pt=p。 p=pnext。 qnext=p。 free(pt)。 } else{ p=p*p。 p。 q=p。 p=pnext。 } } return OK。} 試編寫(xiě)算法，將一個(gè)用循環(huán)鏈表表示的稀疏多項(xiàng)式分解成兩個(gè)多項(xiàng)式，使這兩個(gè)多項(xiàng)式中各自僅含奇次項(xiàng)或偶次項(xiàng)，并要求利用原鏈表中的結(jié)點(diǎn)空間構(gòu)成這兩個(gè)鏈表。解：// 將單鏈表L劃分成2個(gè)單循環(huán)鏈表Status ListDivideInto2CL(LinkedPoly amp。L,LinkedPoly amp。L1){ LinkedPoly p,p1,q,pt。 q=L。 p=Lnext。 p1=L1。 while(p!=L){ if(p%2==0){ pt=p。 p=pnext。 qnext=p。 ptnext=p1next。 p1next=pt。 p1=p1next。 } else{ q=p。 p=pnext。 } } return OK。}第3章 棧和隊(duì)列 (b)所示鐵道進(jìn)行車(chē)廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道），則請(qǐng)回答：(1) 如果進(jìn)站的車(chē)廂序列為123，則可能得到的出站車(chē)廂序列是什么？(2) 如果進(jìn)站的車(chē)廂序列為123456，則能否得到435612和135426的出站序列，并請(qǐng)說(shuō)明為什么不能得到或者如何得到（即寫(xiě)出以 ‘S’表示進(jìn)棧和以 ‘X’表示出棧的棧操作序列）。解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。因?yàn)?356出站說(shuō)明12已經(jīng)在棧中，1不可能先于2出棧。 簡(jiǎn)述棧和線性表的差別。解：線性表是具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 寫(xiě)出下列程序段的輸出結(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è)操作開(kāi)始，為序列不同的起始操作點(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……，說(shuō)明兩個(gè)不同的合法棧操作序列的輸出元素的序列一定不同。 試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序列的一個(gè)排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使。解：。因?yàn)檩斎胄蛄惺菑男〉酱笈帕械?，所以若，則可以理解為通過(guò)輸入序列可以得到輸出序列，顯然通過(guò)序列123是無(wú)法得到312的。所以不可能存在著ijk使。 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算(↑)優(yōu)先關(guān)系的慣例，畫(huà)出對(duì)下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過(guò)程： 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階梵塔問(wèn)題至少要執(zhí)行的move操作的次數(shù)。解： 試將下列遞推過(guò)程改寫(xiě)為遞歸過(guò)程。 void ditui(int n) { int i。 i = n。 while(i1) couti。 }解：void ditui(int j){ if(j1){ coutj。 ditui(j1)。 } return。} 試將下列遞歸過(guò)程改寫(xiě)為非遞歸過(guò)程。 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)行刪除。 寫(xiě)出以下程序段的輸出結(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ì)列得到的輸出序