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