【正文】 t。 } snext=p。 k=1。 } if(!s)return INFEASIBLE。pdatamaxk){ if(pdata=mink){ prev=p。amp。解：// 帶頭結(jié)點(diǎn)的單鏈表的逆置Status ListOppose_L(LinkList amp。C){ LinkList pa,pb,qa,qb。} 假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，請(qǐng)編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。 pa=panext。 free(pb)。} 。 pa=panext。 free(pt)。 } else if([]!=[i]){ ListInsert_Sq(C,k,[i])。 } } =k。amp。 pa=panext。 // 保存pa的前驅(qū)指針 qb=pb。 free(pt)。解：// 在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中Status ListUnion_Sq(SqList amp。A,LinkList amp。 } else{ pt=pa。 q=S。 p=(DuLinkList)malloc(sizeof(DuLNode))。解：// 將單鏈表L劃分成3個(gè)單循環(huán)鏈表Status ListDivideInto3CL(LinkList amp。 p=pnext。)){ q=p。typede struct { //無頭結(jié)點(diǎn)的異或指針雙向鏈表 XorPointer Left, Right。 left=p。試寫一時(shí)間復(fù)雜度O(n)的算法，將L改造為。 i++。 while(q!=L amp。 int last。 if(!) return ERROR。i。amp。 k++。 j++。 } else{ p=p*p。 p1next=pt。 y= ‘k’。 Pop(S,A[n])。由于前n個(gè)操作相同，故此時(shí)兩個(gè)棧（不妨為棧A、B）的存儲(chǔ)情況完全相同，假設(shè)此時(shí)棧頂元素均為a。} 試將下列遞歸過程改寫為非遞歸過程。 sum+=x。 EnQueue(Q, ‘a(chǎn)’)。 EnQueue(Q, d)。 EnQueue(Q, y)。 do{ cinx。 while(i1) couti。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。 }解：stack 簡(jiǎn)述以下算法的功能（棧的元素類型SElemType為int）。 void main() { Stack S。 while(p!=L){ if(p%2==0){ pt=p。 while(p!=L){ if(p==0){ pt=p。 pexp=p2exp。 j++。 p1=。 int i,j。 PolyTerm *p。 }}，稀疏多項(xiàng)式采用的順序存儲(chǔ)結(jié)構(gòu)SqPoly定義為typedef struct { int coef。 else{ pfreq++。 rnextpre=q。 return OK。L39。 return OK。 amp。amp。 p=pnext。 Lnext=L。已知s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。 qbnext=pb。B,LinkList amp。 free(pb)。 free(pt)。B){ LinkList pa,pb,qa,qb,pt。 free(pt)。 // 保存pb的前驅(qū)指針 pa=panext。 k++。 j){ if([i][j]) i++。 free(pt)。 C=A。 else{ ListInsert_Sq(C,k,[i])。 pb=pbnext。 C=A。 } if(!pa)qbnext=pb。注意：?jiǎn)捂湵淼拈L(zhǎng)度值m和n均未顯式存儲(chǔ)。 [i]=[]。 p=pnext。 prev=p。 while(samp。 p=pnext。 } s=lb。 while(pbnext) pb=pbnext。 i++。} 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x)。 return OK。 if(i0||i||k0||k) return INFEASIBLE。 } void AA(LNode *pa, LNode *pb) { //pa和pb分別指向單循環(huán)鏈表中的兩個(gè)結(jié)點(diǎn) BB(pa,pb)。(16) Q=Ppriou。e. 刪除P結(jié)點(diǎn)的語句序列是_______________________。(5) while(P!=NULL) P=Pnext。(8) while(Pnext!=Q) P=Pnext。i) Ins_LinkList(L,i+1,i*2)。單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。 for(i=0。i++){ if(a[i]MAXINT) exit(0)。} 試編寫算法，計(jì)算的值并存入數(shù)組a[0..arrsize1]的第i1個(gè)分量中(i=1,2,…,n)。} Component。 else p[i]=1。 設(shè)有以下三個(gè)函數(shù)： ，請(qǐng)判斷以下斷言正確與否：(1) f(n)是O(g(n))(2) h(n)是O(f(n))(3) g(n)是O(h(n))(4) h(n)是O()(5) h(n)是O(nlogn)解：(1)對(duì) (2)錯(cuò) (3)錯(cuò) (4)對(duì) (5)錯(cuò) 試設(shè)定若干n值，比較兩函數(shù)和的增長(zhǎng)趨勢(shì)，并確定n在什么范圍內(nèi)，函數(shù)的值大于的值。 // n是不小于1的常數(shù) while(x=(y+1)*(y+1)) { y++。 i++) { for(j=i。試確定下列各程序段中前置以記號(hào)的語句的頻度：(1) i=1。(3) switch { case xy: z=yx。e) 操作結(jié)果：用e返回復(fù)數(shù)C的兩個(gè)元素中值較小的一個(gè) }ADT ComplexADT RationalNumber{ 數(shù)據(jù)對(duì)象：D={s,m|s,m為自然數(shù)，且m不為0} 數(shù)據(jù)關(guān)系：R={s,m} 基本操作： InitRationalNumber(amp。 數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。 抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。R,s,m)操作結(jié)果：構(gòu)造一個(gè)有理數(shù)R，其分子和分母分別為s和m DestroyRationalNumber(amp。 break。 k=0。 j=n。 }(8) x=91。解：的增長(zhǎng)趨勢(shì)快。 } for(i=k+1。typedef struct{ int MaleSum。假設(shè)計(jì)算機(jī)中允許的整數(shù)最大值為maxint，則當(dāng)narrsize或?qū)δ硞€(gè)，使時(shí)，應(yīng)按出錯(cuò)處理。 else couta[i] 。i=n。 (3) 在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其前驅(qū)結(jié)點(diǎn)的鏈域的值指示。 for(i=1。(9) while(Pnext!=NULL) P=Pnext。(6) while(Qnext!=NULL) { P=Q。(1) Pnext=Pnextnext。(17) free(P)。 BB(pb,pa)。 for(j=0。} 設(shè)和均為順序表，和分別為和中除去最大共同前綴后的子表。解：int LocateElem_L(LinkList amp。 } return i。 pbnext=hanext。 k=1。 k++。amp。 p=pnext。 while(p){ prev=p。 []=x。解：// 將合并后的結(jié)果放在C表中，并刪除B表Status ListMerge_L(LinkList amp。 pb=B。 while(paamp。 qbnext=Anext。 i++。 while(paamp。 } while(pb){ pt=pb。 else if([i][j]) j++。 } else if([k]!=[i]){ [k]=[i]。 pb=pbnext。 } else{ qa=pa。 pa=A。 } else{ if(padata==qadata){ pt=pa。 return OK。C){ ListCross_L(B,C)。 free(pt)。解：// 在單循環(huán)鏈表S中刪除S的前驅(qū)結(jié)點(diǎn)Status ListDelete_CL(LinkList amp。 return OK。 } if(p==L) ppre=q。 pdata=39。amp。}，“異或指針雙向鏈表”類型XorLinkedList和指針異或函數(shù)XorP定義為：typedef struct XorNode { char data。){ p=。} ，寫出在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)的算法。 qnext=rnext。 // 刪除結(jié)點(diǎn) pprenext=pnext。 int exp。 cout請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù):。 PolyTerm *p。 p2=。 } else{ if(p1coef!=p2coef){ pcoef=(p1coef)(p2coef)。 p++。 p=pnext。 p=pnext。 char x,y。(1) status algo1(Stack S) { int i,n,A[255]。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：兩個(gè)不同的合法（棧操作）序列（對(duì)同一輸入序列）不可能得到相同的輸出元素（注意：在此指的是元素實(shí)體，而不是值）序列。 }解：void ditui(int j){ if(j1){ coutj。 Push(s,x)。 DeQueue(Q, x)。 } }解：隊(duì)列逆置 若以1234作為雙端隊(duì)列的輸入序列，試分別求出滿足以下條件的輸出序列： (1) 能由輸入受限的雙端隊(duì)列得到，但不能由輸出受限的雙端隊(duì)列得到的輸出序列。 DeQueue(Q, x)。 while(!StackEmpty(s)){ Pop(s,x)。 } return。設(shè)兩個(gè)合法序列為：T1=S……X……S…… T2=S……X……X…… 假定前n個(gè)操作都相同，從第n+1個(gè)操作開始，為序列不同的起始操作點(diǎn)。 while(!StackEmpty(S)) { n++。 x= ‘c’。 ptnext=p1next。 free(pt)。 p2++。 p++。 while(iamp。 for(i=0,Pn=0。 =(PolyTerm *)malloc(*sizeof(PolyTerm))。typedef struct { //多項(xiàng)式的順序存儲(chǔ)結(jié)構(gòu) PolyTerm *data。 // 插入到合適的位置 q=Lnext。 } else p=pnext。 設(shè)以帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表表示的線性表。 while(p!=NULL){ VisitingData(pdata)。} XorNode, *XorPointer。z39。){ q=p。} 已知由一個(gè)線性鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如：字母字符、數(shù)字字符和其他字符），試編寫算法將該線性表分割為三個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符。L,ElemType e){ DuLinkList p。 if(S==Snext)return ERROR。 pa=panext。}// 求集合AB，結(jié)果放在A表中，并刪除B表Status ListMinus_L(LinkList amp。試對(duì)順序表編寫實(shí)現(xiàn)上述操作的算法，并分析你的算法的時(shí)間復(fù)雜度（注意：題中沒有特別指明同一表中的元素值各不相同）。 qanext=pa。 qa=pa。 } } } while(pa){ pt=pa。 while(paamp。 } i++。 k++。 qbnext=pb。pb){ if(padatapbdata){ pt=pa。 } } return OK。 } pb=B。pb){ if(padatapbdata){ qa=pa。 return OK。B,LinkList amp。} 試寫一