【正文】 已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。d. 在表尾插入S結(jié)點(diǎn)的語句序列是__________________。(4) Snext=Pnext。(8) while(Pnext!=Q) P=Pnext。(12) L=S。 b. 刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是____________________。(1) P=Pnext。(5) while(P!=NULL) P=Pnext。(8) while(Pnextnext!=Q) P=Pnext。(12) P=L。a. 在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句序列是_______________________。e. 刪除P結(jié)點(diǎn)的語句序列是_______________________。(4) Ppriou=S。(8) Spriou=Ppriou。(12) Pnextpriou=S。(16) Q=Ppriou。(1) Status A(LinkedList L) { //L是無表頭結(jié)點(diǎn)的單鏈表 if(L amp。 P=L。 } return OK。 } void AA(LNode *pa, LNode *pb) { //pa和pb分別指向單循環(huán)鏈表中的兩個結(jié)點(diǎn) BB(pa,pb)。 指出以下算法中的錯誤和低效之處，并將它改寫為一個既正確又高效的算法。countk。 。 if(i0||i||k0||k) return INFEASIBLE。 =。解：Status InsertOrderList(SqList amp。i0,x[i1]。 return OK。解：Status CompareOrderList(SqList amp。 for(i=0。 } if(k) j=1。} 試寫一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作Locate(L,x)。 while(pamp。 } if(!p) return 0。L){ int i=0。 i++。請分析你的算法的時間復(fù)雜度。hc){ LinkList pa,pb。amp。 while(pbnext) pb=pbnext。 panext=hbnext。Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len){ if(i0||j0||len0) return INFEASIBLE。 k++。 } s=lb。 } snext=p。la,LinkList amp。 // 在la表中查找第i個結(jié)點(diǎn) p=la。 p=pnext。 k=1。 k++。 // 將從la中刪除的結(jié)點(diǎn)插入到lb中 if(j=1){ qnext=lb。 while(samp。 } if(!s)return INFEASIBLE。} 試寫一算法，在無頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)線性表操作Insert(L,i,b)，并和在帶頭結(jié)點(diǎn)的動態(tài)單鏈表上實(shí)現(xiàn)相同操作的算法進(jìn)行比較。解：Status ListDelete_L(LinkList amp。 prev=p。pdatamaxk){ if(pdata=mink){ prev=p。 p=pnext。解：void ListDelete_LSameNode(LinkList amp。 p=pnext。amp。 free(q)。 ElemType x。 [i]=[]。解：// 帶頭結(jié)點(diǎn)的單鏈表的逆置Status ListOppose_L(LinkList amp。 Lnext=NULL。 Lnext=q。注意：單鏈表的長度值m和n均未顯式存儲。C){ LinkList pa,pb,qa,qb。 while(paamp。 pa=panext。 } if(!pa)qbnext=pb。} 假設(shè)有兩個按元素值遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構(gòu)，請編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許表中含有值相同的元素）排列的線性表C，并要求利用原表（即A表和B表）的結(jié)點(diǎn)空間構(gòu)造C表。C){ LinkList pa,pb,qa,qb。 // 保存pa的前驅(qū)指針 qb=pb。 C=A。 pa=panext。 pb=pbnext。 pa=panext。 pb=pbnext。 free(pb)。解：// 將A、B求交后的結(jié)果放在C表中Status ListCross_Sq(SqList amp。 while(i amp。 else{ ListInsert_Sq(C,k,[i])。} 。B,LinkList amp。 qa=pa。 C=A。 pa=panext。 pb=pbnext。 pa=panext。 free(pt)。 free(pt)。} ，對順序表重新編寫求得表C的算法。B,SqList amp。 j){ if([i][j]) i++。 } else if([]!=[i]){ ListInsert_Sq(C,k,[i])。}(2)// A、B求交，然后刪除相同元素，將結(jié)果放在A表中Status ListCrossDelSame_Sq(SqList amp。amp。 k++。 } } =k。解： (1)// A、B求交，結(jié)果放在C表中，并刪除相同元素Status ListCrossDelSame_L(LinkList amp。 pa=A。 // 保存pb的前驅(qū)指針 pa=panext。amp。 free(pt)。 free(pt)。 free(pt)。 pa=panext。 pb=pbnext。 free(pb)。B){ LinkList pa,pb,qa,qb,pt。 // 保存pa的前驅(qū)指針 qb=pb。amp。 free(pt)。 free(pt)。 free(pt)。 pa=panext。 pb=pbnext。 free(pb)。解：// 在A中刪除既在B中出現(xiàn)又在C中出現(xiàn)的元素，結(jié)果放在D中Status ListUnion_Sq(SqList amp。C){ SqList Temp。} 。B,LinkList amp。A,LinkList amp。 qa=pa。 while(paamp。 qbnext=pb。 } else{ pt=pa。 } } while(pb){ pt=pb。 } pb=B。已知s為指向鏈表中某個結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。 q=S。 } qnext=pnext。解：// 建立一個空的循環(huán)鏈表Status InitList_DL(DuLinkList amp。 Lnext=L。 p=(DuLinkList)malloc(sizeof(DuLNode))。 Lnext=p。 q=L。 p=pnext。解：// 將單鏈表L劃分成3個單循環(huán)鏈表Status ListDivideInto3CL(LinkList amp。s3){ LinkList p,q,pt1,pt2,pt3。 pt3=s3。amp。 p=pnext。 } else if((pdata=39。 pdata=39。 amp。)){ q=p。 pt2=pt2next。 pt3next=q。 return OK。typede struct { //無頭結(jié)點(diǎn)的異或指針雙向鏈表 XorPointer Left, Right。鏈表L中的每個結(jié)點(diǎn)只含兩個域：data域和LRPtr域，其中LRPtr域存放該結(jié)點(diǎn)的左鄰與右鄰結(jié)點(diǎn)指針（不存在時為NULL）的異或。L,char d){ XorPointer p,left,right。L39。 left=p。||d==39。 while(p!=NULL){ VisitingData(pdata)。 return OK。試寫一時間復(fù)雜度O(n)的算法，將L改造為。 p=Lnext。 p=pnext。 rnextpre=q。 i++。試編寫符合上述要求的Locate操作的算法。 while(p!=L amp。 else{ pfreq++。 while(q!=L amp。 qnext=p。 qprenext=p。 }}，稀疏多項式采用的順序存儲結(jié)構(gòu)SqPoly定義為typedef struct { int coef。 int last。解：typedef struct{ int coef。 int last。 PolyTerm *p。 if(!) return ERROR。i++){ cout請輸入系數(shù):。 p++。 int i,j。i。 Pn=Pn+pcoef*x。L,SqPoly amp。 p1=。amp。 k++。 pexp=p2exp。 j++。 k++。 j++。 k++。 pexp=p2exp。 j++。 struct PolyNode *next。解：Status PolyDifferential(LinkedPoly amp。 while(p!=L){ if(p==0){ pt=p。 } else{ p=p*p。 } } return OK。L1){ LinkedPoly p,p1,q,pt。 while(p!=L){ if(p%2==0){ pt=p。 p1next=pt。 } } return OK。 簡述棧和線性表的差別。 void main() { Stack S。 y= ‘k’。 Pop(S,x)。 Push(S, ‘s’)。 }解：stack 簡述以下算法的功能（棧的元素類型SElemType為int）。 Pop(S,A[n])。 }(2) status algo2(Stack S,int e) { Stack T。 if(d!=e) Push(T,d)。稱可以操作的序列為合法序列（例如，SXSX為合法序列，SXXS為非法序列）。由于前n個操作相同，故此時兩個棧（不妨為棧A、B）的存儲情況完全相同，假設(shè)此時棧頂元素均為a。 試證明：若借助棧由輸入序列12…n得到的輸出序列為(它是輸入序列的一個排列)，則在輸出序列中不可能出現(xiàn)這樣的情形：存在著ijk使。 按照四則運(yùn)算加、減、乘、除和冪運(yùn)算(↑)優(yōu)先關(guān)系的慣例，畫出對下列算術(shù)表達(dá)式求值時操作數(shù)棧和運(yùn)算符棧的變化過程： ABC/D+E↑F解：BC=G G/D=H AH=I E^F=J I+J=K步驟OPTR棧OPND棧輸入字符主要操作1AB*C/D+E^FPUSH(OPND,A)2AB*C/D+E^FPUSH(OPTR,)3AB*C/D+E^FPUSH(OPND,B)4A B*C/D+E^FPUSH(OPTR,*)5*A BC/D+E^FPUSH(OPND,C)6*A B C/D+E^FOperate(B,*,C)7A G/D+E^FPUSH(OPTR,/)8/A GD+E^FPUSH(OPND,D)9/A G D+E^FOperate(G,/,D)10A H+E^FOperate(A,,H)11I+E^FPUSH(OPTR,+)12+IE^FPUSH(OPND,E)13+I E^FPUSH(OPTR,^)14+^I EFPUSH(OPND,F)15+^I E FOperate(E,^,F)16+I JOperate(I,+,J)17KRETURN 試推導(dǎo)求解n階梵塔問題至少要執(zhí)行的move操作的次數(shù)。 while(i1) couti。} 試將下列遞歸過程改寫為非遞歸過程。 if(x==0) sum=0。 }解：void test(int amp。 do{ cinx。 sum+=x。解：棧是一種運(yùn)算受限的線性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。 InitQueue(Q)。 EnQueue(Q, y)。 EnQueue(Q, ‘a(chǎn)’)。 }解：char 簡述以下算法的功能（棧和隊列的元素類型均為int）。 InitStack(S)。 EnQueue(Q, d