【正文】 +...+n)= = = (6) n (7) 向下取整 (8) 1100 假設(shè)n為2的乘冪，并且n2，試求下列算法的時(shí)間復(fù)雜度及變量count的值（以n的函數(shù)形式表示）。 count++。解： n=40 n=16 則對(duì)于同樣的循環(huán)次數(shù)n，在這個(gè)規(guī)模下，第二種算法所花費(fèi)的代價(jià)要大得多。但在n較小的時(shí)候，的值較大。 else return z。 p=new int[k+1]。ik+1。in+1。j++) p[j]=p[j+1]。解：typedef enum{A,B,C,D,E} SchoolName。 SchoolName school。 //男團(tuán)總分 int FemaleSum。 =0。 for(i=0。 } } =+。注意選擇你認(rèn)為較好的出錯(cuò)處理方法。 coutEnter k:。i=k。 } } for(i=0。 } return 0。解：includeincludedefine N 10double polynomail(int a[],int i,double x,int n)。 cout輸入變量的值x:。 if(nN1) exit(0)。i++) cina[i]。 else return a[n]。首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。解：(1) 在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與元素在表中的位置有關(guān)。 (4) 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是插入和刪除首元結(jié)點(diǎn)時(shí)不用進(jìn)行特殊處理。 L=(LinkList)malloc(sizeof(LNode))。i++){ Pnext=(LinkList)malloc(sizeof(LNode))。 for(i=4。i=3。b. 在P結(jié)點(diǎn)前插入S結(jié)點(diǎn)的語(yǔ)句序列是__________________。(2) Pnext=Pnextnext。(6) Snext=NULL。(10) P=Q。解：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)，試從下列提供的答案中選擇合適的語(yǔ)句序列。 d. 刪除首元結(jié)點(diǎn)的語(yǔ)句序列是____________________。(3) Pnext=Pnextnext。 Q=Qnext。(10) Q=P。(14) free(Q)。c. 刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列是_______________________。(2) Ppriou=Pprioupriou。(6) Spriou=P。(10) Ppriounext=P。(14) Pnextpriou=Ppriou。(18) free(Q)。 Lnext) { Q=L。 Pnext=Q。 while(pnext!=q) p=pnext。 }解：(1) 如果L的長(zhǎng)度不小于2，將L的首元結(jié)點(diǎn)變成尾元結(jié)點(diǎn)。a,int i,int k){ //本過(guò)程從順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表a中刪除第i個(gè)元素起的k個(gè)元素 if(i1||k0||i+k) return INFEASIBLE。j=i+1。}解：Status DeleteK(SqList amp。j=k。} 設(shè)順序表va中的數(shù)據(jù)元素遞增有序。 if(==)return(OVERFLOW)。 [i]=x。若空表，則；若=空表，而空表，或者兩者均不為空表，且的首元小于的首元，則；否則。B){ int i,k,j。i++){ if([i][i]) j=1。 if(==) j=0。L,ElemType x){ int i=0。pdata!=x){ p=pnext。} 試寫(xiě)一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線(xiàn)性表操作Length(L)。 if(p) p=pnext。} 已知指針ha和hb分別指向兩個(gè)單鏈表的頭結(jié)點(diǎn)，并且已知兩個(gè)鏈表的長(zhǎng)度分別為m和n。ha,LinkList amp。 pb=hb。 pb=pbnext。 } else{ hc=ha。下列算法是從表la中刪除自第i個(gè)元素起共len個(gè)元素后，將它們插入到表lb中第i個(gè)元素之前。 k=1。 while(k=len){ q=qnext。 while(kj){ s=snext。 return OK。 int k=1。amp。 } if(!p)return INFEASIBLE。amp。 // 完成刪除，注意，i=1的情況需要特殊處理 if(!prev) la=qnext。 } else{ s=lb。kj1){ s=snext。 snext=p。 已知線(xiàn)性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。 if(minkmaxk)return ERROR。 while(pamp。 } else{ prevnext=pnext。 } } return OK。 p=L。 p=pnext。 q=p。解：// 順序表的逆置Status ListOppose_Sq(SqList amp。i。 } return OK。 p=L。 p=pnext。} 設(shè)線(xiàn)性表，試寫(xiě)一個(gè)按下列規(guī)則合并A，B為線(xiàn)性表C的算法，即使得 當(dāng)時(shí)； 當(dāng)時(shí)。A,LinkList amp。 pb=Bnext。pb){ qa=pa。 qbnext=qanext。 free(pb)。A,LinkList amp。 pb=B。 pb=pbnext。amp。 //將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 Anext=qa。 //將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 Anext=qb。 Anext=qa。 Anext=qb。} 假設(shè)以?xún)蓚€(gè)元素依值遞增有序排列的線(xiàn)性表A和B分別表示兩個(gè)集合（即同一表中的元素值各不相同），現(xiàn)要求另辟空間構(gòu)成一個(gè)線(xiàn)性表C，其元素為A和B中元素的交集，且表C中的元素有依值遞增有序排列。B,SqList amp。 j){ if([i][j]) i++。 k++。解：// 將A、B求交后的結(jié)果放在C表中，并刪除B表Status ListCross_L(LinkList amp。 pa=A。 // 保存pb的前驅(qū)指針 pa=panext。amp。 free(pt)。 free(pt)。 pa=panext。 pb=pbnext。 free(pb)。解：(1)// A、B求交，然后刪除相同元素，將結(jié)果放在C表中Status ListCrossDelSame_Sq(SqList amp。 while(i amp。 else{ if(==0){ ListInsert_Sq(C,k,[i])。 } i++。B){ int i=0,j=0,k=0。 else if([i][j]) j++。 k++。} ，對(duì)單鏈表重新編寫(xiě)求得表C的算法。B,LinkList amp。 qa=pa。 C=A。 pa=panext。 pb=pbnext。 pa=panext。 pa=panext。 free(pt)。 free(pt)。}(2)// A、B求交，結(jié)果放在A(yíng)表中，并刪除相同元素Status ListCrossDelSame_L(LinkList amp。 pb=B。 pb=pbnext。 pa=panext。 pb=pbnext。 pa=panext。 pa=panext。 free(pt)。 free(pt)。} 已知A，B和C為三個(gè)遞增有序的線(xiàn)性表，現(xiàn)要求對(duì)A表作如下操作：刪去那些既在B表中出現(xiàn)又在C表中出現(xiàn)的元素。A,SqList amp。ListCross_L(B,C,Temp)。解：// 在A(yíng)中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，并釋放B、CStatus ListUnion_L(LinkList amp。 ListMinus_L(A,B)。 pa=A。 // 保存pb的前驅(qū)指針 pa=panext。pb){ if(pbdatapadata){ pt=pb。 } else if(pbdatapadata){ qa=pa。 qanext=pa。 qbnext=pb。 return OK。S){ LinkList p,q。 while(pnext!=S){ q=p。 return OK。 if(!L) exit(OVERFLOW)。} // 向循環(huán)鏈表中插入一個(gè)結(jié)點(diǎn)Status ListInsert_DL(DuLinkList amp。 pdata=e。} // 將單循環(huán)鏈表改成雙向鏈表Status ListCirToDu(DuLinkList amp。 while(p!=L){ ppre=q。 return OK。s1,LinkList amp。 pt1=s1。039。939。 pt1next=q。 amp。) || (pdata=39。 pdata=39。 qnext=pt2next。 p=pnext。 } } q=L。 struct XorNode *LRPtr。XorPointer XorP(XorPointer p, XorPointer q)。試寫(xiě)一算法按任一方向依次輸出鏈表中各元素的值。l39。 left=NULL。 } } else if(d==39。){ p=。 p=XorP(pLRPtr,right)。 ，寫(xiě)出刪除第i個(gè)結(jié)點(diǎn)的算法。L){ int i。 i=1。 qnextpre=qpre。 rnext=q。} 設(shè)有一個(gè)雙向循環(huán)鏈表，每個(gè)結(jié)點(diǎn)中除有pre，data和next三個(gè)域外，還增設(shè)了一個(gè)訪(fǎng)問(wèn)頻度域freq。L,ElemType e){ DuLinkList p,q。 pdata!=e) p=pnext。 pnextpre=ppre。 qfreqpfreq) q=qnext。 qpre=p。 qpre=p。} PolyTerm。 已知稀疏多項(xiàng)式，其中。} PolyTerm。// 建立一個(gè)多項(xiàng)式Status PolyInit(SqPoly amp。 cin。 for(i=0。 cout請(qǐng)輸入指數(shù):。} // 求多項(xiàng)式的值double PolySum(SqPoly amp。 p=。jpexp。} ，編寫(xiě)求的算法，將結(jié)果多項(xiàng)式存放在新辟的空間中，并分析你的算法的時(shí)間復(fù)雜度。L2){ PolyTerm *p,*p1,*p2。 int i=0,j=0,k=0。 pexp=p1exp。 i++。 k++。 pexp=p1exp。 p2++。 pexp=p1exp。 i++。 k++。 return OK。typedef PolyLink LinkedPoly。 q=L。 qnext=p。 q=p。解：// 將單鏈表L劃分成2個(gè)單循環(huán)鏈表Status ListDivideInto2CL(LinkedPoly amp。 p=Lnext。 qnext=p。 } else{ q=p。解：(1) 123 231 321 213 132 (2) 可以得到135426的出站序列，但不能得到435612的出站序列。棧是限定僅在表尾進(jìn)行插入或刪除操作的線(xiàn)性表。 InitStack(S)。 Push(S, ‘a(chǎn)’)。 Push(S,x)。 printf(y)。 n=0。i=n。 InitStack(T)。 Push(S,d)。解：任何前n個(gè)序列中S的個(gè)數(shù)一定大于X的個(gè)數(shù)。T1為入棧操作，假設(shè)將b壓棧，則T1的輸出順序一定是先b后a；而T2將a退棧，則其輸出順序一定是先a后b。因?yàn)檩斎胄蛄惺菑男〉酱笈帕械模匀?，則可以理解為通過(guò)輸入序列可以得到輸出序列，顯然通過(guò)序列123是無(wú)法得到312的。 void ditui(int n) { int i。 ditui(j1)。sum) { int x。 sum+=x。 InitStack(s)。 }while(x0)。 } DestoryStack(s)。 寫(xiě)出以下程序段的輸出結(jié)果（隊(duì)列中的元素類(lèi)型QElemType為char）。 EnQueue(Q, ‘h’)。 EnQueue(Q, x)。 couty。Q) { Stack S。 Push(S, d)。 (2) 能由輸出受限的雙端隊(duì)列得到，但不能由輸入受限的雙端隊(duì)列得到的輸出