【正文】 amp。pa=panext。} else if(padatapbdata) {u=pa。 pb=pbnext。 delete u。}∥釋放結點空間pcnext=null。請設計算法求出兩個集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。[算法描述]void Difference（LinkListamp。 ∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 pre=La。pa=panext。 ∥處理A，B中元素值相同的結點，應刪除 u=pa。[題目分析]B表的頭結點使用原來A表的頭結點，為C表新申請一個頭結點。 ∥B表初始化 C=new LNode。 ∥暫存p的后繼 if(pdata0) {pnext=Bnext。 }∥將大于等于0的結點鏈入C表,前插法 p=r。[算法描述]ElemType Max (LinkList L ){ if(Lnext==NULL) return NULL。//如果p的值大于pmax的值，則重新賦值 p=pnext。[算法描述]void inverse(LinkList amp。 // q指向*p的后繼 pnext=Lnext。[題目分析]分別查找第一個值mink的結點和第一個值 ≥maxk的結點，再修改指針，刪除值大于mink且小于maxk的所有元素。amp。amp。 // 修改指針 while (q!=p) { s=qnext。[題目分析]知道雙向循環(huán)鏈表中的一個結點，與前驅交換涉及到四個結點（p結點，前驅結點，前驅的前驅結點，后繼結點）六條鏈。 qllink=p； ∥p與其前驅交換 prlinkllink=q； ∥p的后繼的前驅指向原p的前驅 prlink=q； ∥p的后繼指向其原來的前驅}∥算法exchange結束。因此可以考慮設頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數(shù)據(jù)元素時，直接將右端元素左移至值為item的數(shù)據(jù)元素位置。amp。 A[j]==item）j；∥若右端元素為item，指針左移 if（ij）A[i++]=A[j]；}第3章 棧和隊列1．選擇題（1）若讓元素1，2，3，4，5依次進棧，則出棧次序不可能出現(xiàn)在（ ）種情況。（3）數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為（ ）。top=toplink； B．top=toplink。 }則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。 B．設n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。（7）為解決計算機主機與打印機間速度不匹配問題，通常設一個打印數(shù)據(jù)緩沖區(qū)。（8）設棧S和隊列Q的初始狀態(tài)為空，元素eeeee5和e6依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是eeeee5和e1，則棧S的容量至少應該是（?。?V[top]=x。 V[top]=x。（10）設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（?。?shù)據(jù)結構最佳。（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（?。＃?4）棧和隊列的共同點是（?。?。當?shù)?號棧的棧頂指針top[0]等于1時該棧為空，當?shù)?號棧的棧頂指針top[1]等于m時該棧為空。 //棧頂和棧底指針 SElemType *V。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。{[0]=1。,intexit(0)。{casei)∥退棧。switch(i){casecasereturn(1)。判斷?？読ntamp。左棧是通常意義下的棧，而右棧入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。[題目分析]將字符串前一半入棧，然后，棧中元素和字符串后一半進行比較。//假定棧元素的數(shù)據(jù)類型為字符typedef struct{DataType data[StackSize]。int i , len。len=strlen(t)。s, t[i])。if( temp!=S[i])return 1 。{int top=0。 i++) //n個整數(shù)序列作處理。 ｛if(top==maxsize1){cout“棧滿”endl。｝ else //讀入的整數(shù)等于1時退棧。} }}//算法結束。[題目分析]逆波蘭表達式(即后綴表達式)求值規(guī)則如下：設立運算數(shù)棧OPND,對表達式從左到右掃描(讀入)，當表達式中掃描到數(shù)時，壓入OPND棧。｛float OPND[30]。float num=。while(x!=’$’) {switch {case‘0’=x=’9’:while((x=’0’amp。}else //處理小數(shù)部分。amp。 }}//elsepush(OPND,num)。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND))。push(OPND,x2x1)。 case x=‘/’:x1=pop(OPND)。 default: //其它符號不作處理。}//算法結束。這種字符的序號減去字符‘0’的序號得出數(shù)。在拼數(shù)過程中，若遇非數(shù)字字符，表示數(shù)已拼完，將數(shù)壓入棧中，并且將變量num恢復為0，準備下一個數(shù)。①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。int Judge(char A[]) //判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。 j=k=0。 break。} }i++。} }//算法結束。[題目分析]置空隊就是建立一個頭節(jié)點，并把頭尾指針都指向頭節(jié)點，頭節(jié)點是不存放數(shù)據(jù)的；判隊空就是當頭指針等于尾指針時，隊空；入隊時，將新的節(jié)點插入到鏈隊列的尾部，同時將尾指針指向這個節(jié)點；出隊時，刪除的是隊頭節(jié)點，要注意隊列的長度大于1還是等于1的情況，這個時候要注意尾指針的修改，如果等于1，則要刪除尾指針指向的節(jié)點。 //以上是結點類型的定義typedef struct{queuenode *rear。//將隊尾指針指向頭結點while (Qrear!=Qrearnext)//當隊列非空，將隊中元素逐個出隊{s=Qrearnext。int EmptyQueue( LinkQueue *Q){ //判隊空。//申請新結點pdata=x。Qrear=p。p=Qrearnextnext。}else}（7）假設以數(shù)組Q[m]存放循環(huán)隊列中的元素, 同時設置一個標志tag，以tag == 0和tag == 1來區(qū)別在隊頭指針(front)和隊尾指針(rear)相等時，隊列狀態(tài)為“空”還是“滿”。return (==)) cout隊列已滿endl。if(==0) =1。 exit(0)。[題目分析] 用一維數(shù)組 v[0..M1]實現(xiàn)循環(huán)隊列，其中M是隊列長度。[算法描述]①define M 隊列可能達到的最大長度typedef struct{elemtp data[M]。{if (==) { cout隊列空endl。return([(+1+M)%M])。 exit(0)。}// 結束從隊頭插入算法。 else if(m!=0amp。 }//算法結束① Ack(2,1)的計算過程Ack(2,1)= Ack(1,Ack(2,0)) //因m0,n0而得 = Ack(1,Ack(1,1)) //因m0,n=0而得 = Ack(1,Ack(0,Ack(1,0))) // 因m0,n0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m0,n=0而得 = Ack(1,Ack(0,2)) // 因m=0而得 = Ack(1,3) // 因m=0而得 = Ack(0,Ack(1,2)) //因m0,n0而得 = Ack(0,Ack(0,Ack(1,1))) //因m0,n0而得 = Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m0,n0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得②int Ackerman(int m, int n){int akm[M][N]。j++) akm[0][j]=j+1。for(j=1。}//算法結束（10）已知f為單鏈表的表頭指針, 鏈表中存儲的都是整型數(shù)據(jù)，試寫出實現(xiàn)下列運算的遞歸算法： ① 求鏈表中的最大整數(shù)；② 求鏈表的結點個數(shù)；③ 求所有整數(shù)的平均值。 }}②int GetLength(LinkList p){ if(!pnext) return 1。 return (ave*(n1)+pdata)/n。A．012345678999 B．012121111212 C．011234223456 D．0123012322345答案：C（4）串“ababaabab”的nextval為（ ）。A．808 B．818 C．1010 D．1020答案：B解釋：以行序為主，則LOC[5,5]=[（51）*100+（51）]*2+10=818。A．13 B．32 C．33 D．40答案：C（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（ij）的位置k的關系為（ ）。A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9]答案：B解釋：設數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲，元素A[8,5]的起始地址為：M+[（80）*10+（51）]*1=M+84；若數(shù)組按列先存儲，易計算出元素A[3,10]的起始地址為：M+[（101）*9+（30）]*1=M+84。取i=j=1，易知A[1,1]的的下標為1，四個選項中僅有A選項能確定的值為1，故選A。A．(g) B．(d) C．c D．d答案：D解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。A．1和1 B．1和3 C．1和2 D．2和3 答案：C解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指廣義表中所含元素的個數(shù)。答案：① p的nextval函數(shù)值為0110132。（1）242 （2）22 （3）s+182 （4）s+142(4)請將香蕉banana用工具 H( )—Head( )，T( )—Tail( )從L中取出。遇其它符號不作處理，直至輸入字符串結束。num[i]++；｝ // 數(shù)字字符　　 else　if（‘A’=ch=‘Z’）｛i=ch65+10。[題目分析]實現(xiàn)字符串的逆置并不難，但本題“要求不另設串存儲空間”來實現(xiàn)字符串逆序存儲，即第一個輸入的字符最后存儲，最后輸入的字符先存儲，使用遞歸可容易做到。//需要使用靜態(tài)變量cinch。.39。\039。（說明：不得使用任何庫函數(shù)）[題目分析]本題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。{int i=1,x=0。}while(*p!=’\0’amp。} //查pos位置 //若pos小于串s長度，則查到pos位置時，i=pos。exit(0)。 i++。) {q++。 for(j=i。}//串s的pos后的子串右移，空出串t的位置。j++) *p=*q。（4）已知字符串S1中存放一段英文，寫出算法