【正文】 驅結點的指針域。 p=pnext。 if(S==Snext)return ERROR。} 假設某個單向循環(huán)鏈表的長度大于1，且表中既無頭結點也無頭指針。 free(pt)。 free(pt)。 pa=panext。 pb=pbnext。 pb=pbnext。 pb=B。}// 求集合AB，結果放在A表中，并刪除B表Status ListMinus_L(LinkList amp。A,LinkList amp。 ListMinus_L(A,Temp,D)。B,SqList amp。試對順序表編寫實現(xiàn)上述操作的算法，并分析你的算法的時間復雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。 } pb=B。 } while(pb){ pt=pb。 } } } while(pa){ pt=pa。 qanext=pa。 qbnext=pb。 qanext=pa。 while(paamp。 qa=pa。A,LinkList amp。 } pb=B。 } while(pb){ pt=pb。 } } } while(pa){ pt=pa。 qanext=pa。 qbnext=pb。 qanext=pa。 while(paamp。 // 保存pa的前驅指針 qb=pb。C){ LinkList pa,pb,qa,qb,pt。(1) 假設在同一表（A或B）中可能存在值相同的元素，但要求新生成的表C中的元素值各不相同；(2) 利用原表（A表或B表）中的結點構成表C，并釋放A表中的無用結點空間。 } i++。 else{ if(k==0){ [k]=[i]。 while(i amp。 } } return OK。 k++。amp。A,SqList amp。 return OK。 qbnext=pb。 qanext=pa。 } else{ qa=pa。 } else if(padatapbdata){ pt=pb。pb){ if(padatapbdata){ pt=pa。 pb=pbnext。 pb=B。A,LinkList amp。 } } return OK。 else if([i][j]) j++。C){ int i=0,j=0,k=0。試對順序表編寫求C的算法。 } pb=B。 } while(pb){ qb=pb。 } } while(pa){ qa=pa。 } else{ qb=pb。pb){ if(padatapbdata){ qa=pa。 Anext=NULL。 qa=pa。B,LinkList amp。 return OK。 qanext=qb。 qb=pb。 C=A。B,LinkList amp。線性表A，B和C均以單鏈表作存儲結構，且C表利用A表和B表中的結點空間構成。 qnext=Lnext。 p=pnext。} 試寫一算法，對單鏈表實現(xiàn)就地逆置。i++){ x=[i]。L){ int i。 p=pnext。 if(pamp。 prev=p。} ，試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結點空間，并分析你的算法的時間復雜度。 q=p。amp。 p=L。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素），同時釋放被刪結點空間，并分析你的算法的時間復雜度（注意，mink和maxk是給定的兩個參變量，它們的值可以和表中的元素相同，也可以不同）。 //完成插入 } return OK。 k++。 k=1。 else prevnext=qnext。klen){ q=pnext。 // 在la表中查找第i+len1個結點 q=p。ki){ prev=p。 if(i0||j0||len0) return INFEASIBLE。}解：Status DeleteAndInsertSub(LinkList amp。 k++。 k++。 while(ki){ p=pnext。試問此算法是否正確？若有錯，請改正之。 while(panext) pa=panext。 } if(!panext){ hc=hb。 while(panextamp。hb,LinkList amp。試寫一算法將這兩個鏈表連接在一起，假設指針hc指向連接后的鏈表的頭結點，并要求算法以盡可能短的時間完成連接運算。 while(p){ p=pnext。解：//返回單鏈表的長度int ListLength_L(LinkList amp。 i++。 LinkList p=L。 return j。 if([i][i]) j=1。 k=?:。試寫一個比較，大小的算法。 ++。 for(i=。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。j++) [j+i]=[j+i+k]。a,int i,int k){ //從順序存儲結構的線性表a中刪除第i個元素起的k個元素 //注意i的編號從0開始 int j。j) [ji]=[j]。//參數(shù)不合法 else {for(count=1。 (2) 將單循環(huán)鏈表拆成兩個單循環(huán)鏈表。 pnext =s。 Qnext=NULL。 L=Lnext。解：a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 簡述以下算法的功能。(15) Q=Pnext。(11) Pnextpriou=P。(7) Snext=Pnext。(3) Pnext=S。d. 刪除P結點的直接前驅結點的語句序列是_______________________。解：a. (11) (3) (14) b. (10) (12) (8) (3) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14) 已知P結點是某雙向鏈表的中間結點，試從下列提供的答案中選擇合適的語句序列。(11) Q=Pnext。 }(7) while(Pnext!=Q) P=Pnext。(4) P=Pnextnext。e. 刪除尾元結點的語句序列是____________________。 a. 刪除P結點的直接后繼結點的語句序列是____________________。(11) P=L。(7) Q=P。(3) Pnext=Snext。c. 在表首插入S結點的語句序列是__________________。i++) Del_LinkList(L,i)。i=1。 P=Pnext。 P=L。 在什么情況下用順序表比鏈表好？解：當線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲的時候，用順序表比用鏈表好，其特點是可以進行隨機存取。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。頭結點是在首元結點之前附設的一個結點，該結點不存儲數(shù)據(jù)元素，其指針域指向首元結點，其作用主要是為了方便對鏈表的操作。}本算法的時間復雜度為o(n)。 coutThe polynomail value is polynomail(a,n,x,n)endl。 cout輸入多項式的系數(shù)a[0]a[n]:。 cinx。int main(){ double x。} 試編寫算法求一元多項式的值的值，并確定算法中每一語句的執(zhí)行次數(shù)和整個算法的時間復雜度。i=k。i++){ if(i==0) a[i]=1。 cink。解：includeincludedefine MAXINT 65535define ArrSize 100int fun(int i)。 return temp。in。 =0。 //女團總分 int TotalSum。 int score。typedef enum{Female,Male} SexType。 p[k]=2*p[k1]x。i++){ x=p[0]。i++){ if(ik1) p[i]=0。 if(!p) exit(OVERFLOW)。} 已知k階斐波那契序列的定義為 ，…，； ， 試編寫求k階斐波那契序列的第m項值的函數(shù)算法，k和m均以值調用的形式在函數(shù)參數(shù)表中出現(xiàn)。 當n438時， 判斷下列各對函數(shù)和，當時，哪個函數(shù)增長更快？(1) ，(2) ，(3) ，(4) ，解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 試用數(shù)學歸納法證明：(1) (2) (3) (4) 試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)X，Y和Z的值解：int max3(int x,int y,int z){ if(xy) if(xz) return x。故在這個規(guī)模下，第一種算法更適宜。 }return count。int Time(int n) { count = 0。 while(y0) { if(x100) { x = 10。 y=0。 j=0。 j++) { for(k=1。 }(5) for(i=1。 i=n。 while (i=n1) { i++。 i++。 i++。 設n為正整數(shù)。試討論這三種方法的優(yōu)缺點。解：(1)exit常用于異常錯誤處理，它可以強行中斷程序的執(zhí)行，返回操作系統(tǒng)。 break。 (a[i]!=x))。 }(2) i=0。(1) product=1。e) 操作結果：用e返回有理數(shù)R的第k元的值 Put(amp。e) 操作結果：用e返回復數(shù)C的兩個元素中值較大的一個 Min(C,amp。C,re,im)操作結果：構造一個復數(shù)C，其實部和虛部分別為re和im DestroyCmoplex(amp。在定義抽象數(shù)據(jù)類型中的數(shù)據(jù)部分和操作部分時，要求只定義到數(shù)據(jù)的邏輯結構和操作說明，不考慮數(shù)據(jù)的存儲結構和操作的具體實現(xiàn)，這樣抽象層次更高，更能為其他用戶提供良好的使用接口。 試描述數(shù)據(jù)結構和抽象數(shù)據(jù)類型的概念與程序設計語言中數(shù)據(jù)類型概念的區(qū)別。 存儲結構是數(shù)據(jù)結構在計算機中的表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。解：數(shù)據(jù)是對客觀事物的符號表示。 數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。是對一般數(shù)據(jù)類型的擴展。抽象數(shù)據(jù)類型通常由編程者定義，包括定義它所使用的數(shù)據(jù)和在這些數(shù)據(jù)上所進行的操作。 解：ADT Complex{ 數(shù)據(jù)對象：D={r,i|r,i為實數(shù)} 數(shù)據(jù)關系：R={r,i} 基本操作： InitComplex(amp。C,k,e) 操作結果：改變復數(shù)C的第k元的值為e IsAscending(C) 操作結果：如果復數(shù)C的兩個元素按升序排列，則返回1，否則返回0 IsDescending(C) 操作結果：如果復數(shù)C的兩個元素按降序排列，則返回1，否則返回0 Max(C,amp。R)操作結果：銷毀有理數(shù)R Get(R,k,amp。e) 操作結果：用e返回有理數(shù)R的兩個元素中值較小的一個 }ADT RationalNumber 試畫出與下列程序段等價的框圖。 i++。amp。 case x=y: z=abs(x*y)。試討論這三種方法各自的優(yōu)缺點。 在程序設計中，可采用下列三種方法實現(xiàn)輸出和輸入：(1) 通過scanf和printf語句；(2) 通過函數(shù)的參數(shù)顯式傳遞；(3) 通過全局變量隱式傳遞。 (3)通過全局變量的隱式傳遞進行輸入輸出最為方便，只需修改變量的值即可，但過多的全局變量使程序的維護較為困難。 while(i=n1){ k += 10*i。 do { k += 10*i。 k=0。 for(i=1。 j++) k++。 j=i。 }(6) i=1。 }(7) x=n。 y=100。 }解：(1) n1 (2) n1 (3) n1 (4) n+(n1)+(n2)+...+1= (5) 1+(1+2)+(1+2+3)+...+(1+2+3+