【正文】 ext=qprenext。 qprenext=p。 ppre=qpre。 qpre=p。 } return p。 }}　　稀疏多項式采用的順序存儲結(jié)構(gòu)SqPoly定義為　　typedef struct {　　 int coef?！　? int exp?！　 PolyTerm。　　typedef struct { //多項式的順序存儲結(jié)構(gòu)　　 PolyTerm *data?！　? int last?！　 SqPoly。 已知稀疏多項式其中試采用存儲量同多項式項數(shù)m成正比的順序存儲結(jié)構(gòu)編寫求的算法（為給定值）并分析你的算法的時間復雜度　　解：typedef struct{ int coef。 int exp。} PolyTerm。typedef struct{ PolyTerm *data。 int last。} SqPoly。// 建立一個多項式Status PolyInit(SqPoly amp。L){ int i。 PolyTerm *p。 cout請輸入多項式的項數(shù):。 cin。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。 if(!) return ERROR。 p=。 for(i=0。i。i++){ cout請輸入系數(shù):。 cinpcoef。 cout請輸入指數(shù):。 cinpexp。 p++。 } return OK。} // 求多項式的值double PolySum(SqPoly amp。Ldouble x0){ double Pnx。 int ij。 PolyTerm *p。 p=。 for(i=0Pn=0。i。i++p++){ for(j=0x=1。jpexp。j++) x=x*x0。 Pn=Pn+pcoef*x。 } return Pn。} 編寫求的算法將結(jié)果多項式存放在新辟的空間中并分析你的算法的時間復雜度　　解：// 求兩多項式的差Status PolyMinus(SqPoly amp。LSqPoly amp。L1SqPoly amp。L2){ PolyTerm *p*p1*p2。 p=。 p1=。 p2=。 int i=0j=0k=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。}　　稀疏多項式采用的循環(huán)鏈表存儲結(jié)構(gòu)LinkedPoly定義為　　typedef struct PolyNode {　　 PolyTerm data。　　 struct PolyNode *next。　　} PolyNode *PolyLink。　　typedef PolyLink LinkedPoly。 試以循環(huán)鏈表作稀疏多項式的存儲結(jié)構(gòu)編寫求其導函數(shù)的方法要求利用原多項式中的結(jié)點空間存放其導函數(shù)多項式同時釋放所有無用結(jié)點　　解：Status PolyDifferential(LinkedPoly amp。L){ LinkedPoly pqpt。 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。} 試編寫算法將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式使這兩個多項式中各自僅含奇次項或偶次項并要求利用原鏈表中的結(jié)點空間構(gòu)成這兩個鏈表　　解：// 將單鏈表L劃分成2個單循環(huán)鏈表Status ListDivideInto2CL(LinkedPoly amp。LLinkedPoly amp。L1){ LinkedPoly pp1qpt。 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章 棧和隊列 (b)所示鐵道進行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道）則請回答：　　(1) 如果進站的車廂序列為123則可能得到的出站車廂序列是什么？　　(2) 如果進站的車廂序列為123456則能否得到435612和135426的出站序列并請說明為什么不能得到或者如何得到（即寫出以 39。S39。表示進棧和以 39。X39。表示出棧的棧操作序列）　　解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列但不能得到435612的出站序列因為4356出站說明12已經(jīng)在棧中1不可能先于2出棧 簡述棧和線性表的差別　　解：線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列棧是限定僅在表尾進行插入或刪除操作的線性表 寫出下列程序段的輸出結(jié)果（棧的元素類型SElemType為char） void main() { Stack S。 char xy。 InitStack(S)。 x= 39。c39。 y= 39。k39。 Push(Sx)。 Push(S 39。a39。)。 Push(Sy)。 Pop(Sx)。 Push(S 39。t39。)。 Push(Sx)。 Pop(Sx)。 Push(S 39。s39。)。 while(!StackEmpty(S)) { Pop(Sy)。 printf(y)。 } printf(x)。 }　　解：stack 簡述以下算法的功能（棧的元素類型SElemType為int）　　(1) status algo1(Stack S)　　 {　　 int inA[255]?！　? n=0?！　? while(!StackEmpty(S)) { n++。 Pop(SA[n])。 }　　 for(i=1。i=n。i++) Push(SA[i])。　　 }　　(2) status algo2(Stack Sint e)　　 {　　 Stack T。 int d?！　? InitStack(T)?！　? while(!StackEmpty(S)){　　 Pop(Sd)?！　? if(d!=e) Push(Td)。　　 }　　 while(!StackEmpty(T)){　　 Pop(Td)?！　? Push(Sd)。　　 }　　 }　　解：(1) 棧中的數(shù)據(jù)元素逆置 (2) 如果棧中存在元素e將其從棧中清除 假設(shè)以S和X分別表示入棧和出棧的操作則初態(tài)和終態(tài)均為空棧的入棧和出棧的操作序列可以表示為僅由S和X組成的序列稱可以操作的序列為合法序列（例如SXSX為合法序列SXXS為非法序列）試給出區(qū)分給定序列為合法序列或非法序列的一般準則并證明：兩個不同的合法（棧操作）序列（對同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實體而不是值）序列　　解：任何前n個序列中S的個數(shù)一定大于X的個數(shù)　　設(shè)兩個合法序列為：　　T1=S......X......S...... T2=S......X......X...... 假定前n個操作都相同從第n+1個操作開始為序列不同的起始操作點由于前n個操作相同故此時兩個棧（不妨為棧A、B）的存儲情況完全相同假設(shè)此時棧頂元素均為a　　第n+1個操作不同不妨T1的第n+1個操作為ST2的第n+1個操作為XT1為入棧操作假設(shè)將b壓棧則T1的輸出順序一定是先b后a；而T2將a退棧則其輸出順序一定是先a后b由于T1的輸出為......ba......而T2的輸出順序為......ab......說明兩個不同的合法棧操作序列的輸出元素的序列一定不同 試證明：若借助棧由輸入序列12...n得到的輸出序列為(它是輸入序列的一個排列)則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使　　解：因為輸入序列是從小到大排列的所以若則可以理解為通過輸入序列可以得到輸出序列顯然通過序列123是無法得到312的所以不可能存在著ijk使 按照四則運算加、減、乘、除和冪運算(↑)優(yōu)先關(guān)系的慣例畫出對下列算術(shù)表達式求值時操作數(shù)棧和運算符棧的變化過程： ABC/D+E↑F　　解：BC=G G/D=H AH=I E^F=J I+J=K步驟
OPTR棧
OPND棧
輸入字符
主要操作
1
AB*C/D+E^F
PUSH(OPNDA)
2
A
B*C/D+E^F
PUSH(OPTR)
3
A
B*C/D+E^F
PUSH(OPNDB)
4
A B
*C/D+E^F
PUSH(OPTR*)
5
*
A B
C/D+E^F
PUSH(OPNDC)
6
*
A B C
/D+E^F
Operate(B*C)
7
A G
/D+E^F
PUSH(OPTR/)
8
/
A G
D+E^F
PUSH(OPNDD)
9
/
A G D
+E^F
Operate(G/D)
10
A H
+E^F
Operate(AH)
11
I
+E^F
PUSH(OPTR+)
12
+
I
E^F
PUSH(OPNDE)
13
+
I E
^F
PUSH(OPTR^)
14
+^
I E
F
PUSH(OPNDF)
15
+^
I E F
Operate(E^F)
16
+
I J
Operate(I+J)
17
K
RETURN
試推導求解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(sx)。 }while(x0)。 while(!StackEmpty(s)){ Pop(sx)。 sum+=x。 coutsumendl。 } DestoryStack(s)。} 簡述隊列和堆棧這兩種數(shù)據(jù)類型的相同點和差異處　　解：棧是一種運算受限的線性表其限制是僅允許在表的一端進行插入和刪除運算　　隊列也是一種運算受限的線性表其限制是僅允許在表的一端進行插入而在表的另一端進行刪除 寫出以下程序段的輸出結(jié)果（隊列中的元素類型QElemType為char） void main() { Queue Q。 InitQueue(Q)。 char x= 39。e39。