【正文】 。注意選擇你認(rèn)為較好的輸入和輸出方法。本題的輸入為，和，輸出為。解：includeincludedefine N 10double polynomail(int a[],int i,double x,int n)。int main(){ double x。 int n,i。 int a[N]。 cout輸入變量的值x:。 cinx。 cout輸入多項(xiàng)式的階次n:。 cinn。 if(nN1) exit(0)。 cout輸入多項(xiàng)式的系數(shù)a[0]a[n]:。 for(i=0。i=n。i++) cina[i]。 coutThe polynomail value is polynomail(a,n,x,n)endl。 return 0。}double polynomail(int a[],int i,double x,int n){ if(i0) return a[ni]+polynomail(a,i1,x,n)*x。 else return a[n]。}本算法的時(shí)間復(fù)雜度為o(n)。第2章 線性表 描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。解：頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。頭結(jié)點(diǎn)是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，其指針域指向首元結(jié)點(diǎn)，其作用主要是為了方便對(duì)鏈表的操作。它可以對(duì)空表、非空表以及首元結(jié)點(diǎn)的操作進(jìn)行統(tǒng)一處理。 填空題。解：(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素在表中的位置有關(guān)。 (2) 順序表中邏輯上相鄰的元素的物理位置必定緊鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。 在什么情況下用順序表比鏈表好？解：當(dāng)線性表的數(shù)據(jù)元素在物理位置上是連續(xù)存儲(chǔ)的時(shí)候，用順序表比用鏈表好，其特點(diǎn)是可以進(jìn)行隨機(jī)存取。 對(duì)以下單鏈表分別執(zhí)行下列各程序段，并畫出結(jié)果示意圖。解： 畫出執(zhí)行下列各行語句后各指針及鏈表的示意圖。 L=(LinkList)malloc(sizeof(LNode))。 P=L。 for(i=1。i=4。i++){ Pnext=(LinkList)malloc(sizeof(LNode))。 P=Pnext。 Pdata=i*21。 } Pnext=NULL。 for(i=4。i=1。i) Ins_LinkList(L,i+1,i*2)。 for(i=1。i=3。i++) Del_LinkList(L,i)。解： 已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是__________________。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是__________________。c. 在表首插入S結(jié)點(diǎn)的語句序列是__________________。d. 在表尾插入S結(jié)點(diǎn)的語句序列是__________________。(1) Pnext=S。(2) Pnext=Pnextnext。(3) Pnext=Snext。(4) Snext=Pnext。(5) Snext=L。(6) Snext=NULL。(7) Q=P。(8) while(Pnext!=Q) P=Pnext。(9) while(Pnext!=NULL) P=Pnext。(10) P=Q。(11) P=L。(12) L=S。(13) L=P。解：a. (4) (1) b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6) 已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。 a. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是____________________。 b. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是____________________。 c. 刪除P結(jié)點(diǎn)的語句序列是____________________。 d. 刪除首元結(jié)點(diǎn)的語句序列是____________________。e. 刪除尾元結(jié)點(diǎn)的語句序列是____________________。(1) P=Pnext。(2) Pnext=P。(3) Pnext=Pnextnext。(4) P=Pnextnext。(5) while(P!=NULL) P=Pnext。(6) while(Qnext!=NULL) { P=Q。 Q=Qnext。 }(7) while(Pnext!=Q) P=Pnext。(8) while(Pnextnext!=Q) P=Pnext。(9) while(Pnextnext!=NULL) P=Pnext。(10) Q=P。(11) Q=Pnext。(12) P=L。(13) L=Lnext。(14) free(Q)。解：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)，試從下列提供的答案中選擇合適的語句序列。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是_______________________。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語句序列是_______________________。c. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是_______________________。d. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_______________________。e. 刪除P結(jié)點(diǎn)的語句序列是_______________________。(1) Pnext=Pnextnext。(2) Ppriou=Pprioupriou。(3) Pnext=S。(4) Ppriou=S。(5) Snext=P。(6) Spriou=P。(7) Snext=Pnext。(8) Spriou=Ppriou。(9) Ppriounext=Pnext。(10) Ppriounext=P。(11) Pnextpriou=P。(12) Pnextpriou=S。(13) Ppriounext=S。(14) Pnextpriou=Ppriou。(15) Q=Pnext。(16) Q=Ppriou。(17) free(P)。(18) free(Q)。解：a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 簡(jiǎn)述以下算法的功能。(1) Status A(LinkedList L) { //L是無表頭結(jié)點(diǎn)的單鏈表 if(L amp。amp。 Lnext) { Q=L。 L=Lnext。 P=L。 while(Pnext) P=Pnext。 Pnext=Q。 Qnext=NULL。 } return OK。 }(2) void BB(LNode *s, LNode *q) { p=s。 while(pnext!=q) p=pnext。 pnext =s。 } void AA(LNode *pa, LNode *pb) { //pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn) BB(pa,pb)。 BB(pb,pa)。 }解：(1) 如果L的長(zhǎng)度不小于2，將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。 (2) 將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表。 指出以下算法中的錯(cuò)誤和低效之處，并將它改寫為一個(gè)既正確又高效的算法。Status DeleteK(SqList amp。a,int i,int k){ //本過程從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素 if(i1||k0||i+k) return INFEASIBLE。//參數(shù)不合法 else {for(count=1。countk。count++){ //刪除第一個(gè)元素 for(j=。j=i+1。j) [ji]=[j]。 。 } return OK。}解：Status DeleteK(SqList amp。a,int i,int k){ //從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素 //注意i的編號(hào)從0開始 int j。 if(i0||i||k0||k) return INFEASIBLE。 for(j=0。j=k。j++) [j+i]=[j+i+k]。 =。 return OK。} 設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。解：Status InsertOrderList(SqList amp。va,ElemType x){ //在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i。 if(==)return(OVERFLOW)。 for(i=。i0,x[i1]。i) [i]=[i1]。 [i]=x。 ++。 return OK。} 設(shè)和均為順序表，和分別為和中除去最大共同前綴后的子表。若空表，則；若=空表，而空表，或者兩者均不為空表，且的首元小于的首元，則；否則。試寫一個(gè)比較，大小的算法。解：Status CompareOrderList(SqList amp。A,SqList amp。B){ int i,k,j。 k=?:。 for(i=0。ik。i++){ if([i][i]) j=1。 if([i][i]) j=1。 } if(k) j=1。 if(k) j=1。 if(==) j=0。 return j。} 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x)。解：int LocateElem_L(LinkList amp。L,ElemType x){ int i=0。 LinkList p=L。 while(pamp。amp。pdata!=x){ p=pnext。 i++。 } if(!p) return 0。 else return i。} 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Length(L)。解：//返回單鏈表的長(zhǎng)度int ListLength_L(LinkList amp。L){ int i=0。 LinkList p=L。 if(p) p=pnext。 while(p){ p=pnext。 i++。 } return i。} 已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和n。試寫一算法將這兩個(gè)鏈表連接在一起，假設(shè)指針hc指向連接后的鏈表的頭結(jié)點(diǎn)，并要求算法以盡可能短的時(shí)間完成連接運(yùn)算。請(qǐng)分析你的算法的時(shí)間復(fù)雜度。解：void MergeList_L(LinkList amp。ha,LinkList amp。hb,LinkList amp。hc){ LinkList pa,pb。 pa=ha。 pb=hb。 while(panextamp。amp。pbnext){ pa=panext。 pb=pbnext。 } if(!panext){ hc=hb。 while(pbnext) pb=pbnext。 pbnext=hanext。 } else{ hc=ha。 while(panext) pa=panext。 panext=hbnext。 }} 已知指針la和lb分別指向兩個(gè)無頭結(jié)點(diǎn)單鏈表中的首元結(jié)點(diǎn)。下列算法是從表la中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表lb中第i個(gè)元素之前。試問此算法是否正確？若有錯(cuò)，請(qǐng)改正之。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len){ if(i0||j0||len0) return INFEASIBLE。 p=la。 k=1。 while(ki){ p=pnext。 k++。 } q=p。 while(k=len){ q=qnext。 k++。 } s=lb。 k=1。 while(kj){ s=snext。 k++。 } snext=p。 qnext=snext。 return OK。}解：Status De