【正文】 } =+。 return temp。} 試編寫(xiě)算法計(jì)算的值并存入數(shù)組a[0..arrsize1]的第i1個(gè)分量中(i=12...n)假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為maxint則當(dāng)narrsize或?qū)δ硞€(gè)使時(shí)應(yīng)按出錯(cuò)處理注意選擇你認(rèn)為較好的出錯(cuò)處理方法　　解：includeincludedefine MAXINT 65535define ArrSize 100int fun(int i)。int main(){ int ik。 int a[ArrSize]。 coutEnter k:。 cink。 if(kArrSize1) exit(0)。 for(i=0。i=k。i++){ if(i==0) a[i]=1。 else{ if(2*i*a[i1]MAXINT) exit(0)。 else a[i]=2*i*a[i1]。 } } for(i=0。i=k。i++){ if(a[i]MAXINT) exit(0)。 else couta[i] 。 } return 0。} 試編寫(xiě)算法求一元多項(xiàng)式的值的值并確定算法中每一語(yǔ)句的執(zhí)行次數(shù)和整個(gè)算法的時(shí)間復(fù)雜度注意選擇你認(rèn)為較好的輸入和輸出方法本題的輸入為和輸出為　　解：includeincludedefine N 10double polynomail(int a[]int idouble xint n)。int main(){ double x。 int ni。 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(anxn)endl。 return 0。}double polynomail(int a[]int idouble xint n){ if(i0) return a[ni]+polynomail(ai1xn)*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í)行下列各程序段并畫(huà)出結(jié)果示意圖　　解： 畫(huà)出執(zhí)行下列各行語(yǔ)句后各指針及鏈表的示意圖 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(Li+1i*2)。 for(i=1。i=3。i++) Del_LinkList(Li)。　　解： 已知L是無(wú)表頭結(jié)點(diǎn)的單鏈表且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)試從下列提供的答案中選擇合適的語(yǔ)句序列 a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是__________________ b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是__________________ c. 在表首插入S結(jié)點(diǎn)的語(yǔ)句序列是__________________ d. 在表尾插入S結(jié)點(diǎn)的語(yǔ)句序列是__________________ (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?！　〗猓篴. (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)試從下列提供的答案中選擇合適的語(yǔ)句序列 a. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是____________________ b. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是____________________ c. 刪除P結(jié)點(diǎn)的語(yǔ)句序列是____________________ d. 刪除首元結(jié)點(diǎn)的語(yǔ)句序列是____________________ e. 刪除尾元結(jié)點(diǎn)的語(yǔ)句序列是____________________ (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)?！　〗猓篴. (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)試從下列提供的答案中選擇合適的語(yǔ)句序列 a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語(yǔ)句序列是_______________________ b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是_______________________ c. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是_______________________ d. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列是_______________________ e. 刪除P結(jié)點(diǎn)的語(yǔ)句序列是_______________________ (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)?！　〗猓篴. (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是無(wú)表頭結(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(papb)。 BB(pbpa)。 }　　　　解：(1) 如果L的長(zhǎng)度不小于2將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn) (2) 將單循環(huán)鏈表拆成兩個(gè)單循環(huán)鏈表 指出以下算法中的錯(cuò)誤和低效之處并將它改寫(xiě)為一個(gè)既正確又高效的算法Status DeleteK(SqList amp。aint iint k){ //本過(guò)程從順序存儲(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。aint iint k){ //從順序存儲(chǔ)結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素 //注意i的編號(hào)從0開(kāi)始 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ù)元素遞增有序試寫(xiě)一算法將x插入到順序表的適當(dāng)位置上以保持該表的有序性　　解：Status InsertOrderList(SqList amp。vaElemType x){ //在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i。 if(==)return(OVERFLOW)。 for(i=。i0x[i1]。i) [i]=[i1]。 [i]=x。 ++。 return OK。} 設(shè)和均為順序表和分別為和中除去最大共同前綴后的子表若空表則；若=空表而空表或者兩者均不為空表且的首元小于的首元?jiǎng)t；否則試寫(xiě)一個(gè)比較大小的算法　　解：Status CompareOrderList(SqList amp。ASqList amp。B){ int ikj。 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。} 試寫(xiě)一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(Lx)。　　解：int LocateElem_L(LinkList amp。LElemType x){ int i=0。 LinkList p=L。