【正文】 要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。當(dāng)一個表到達表尾結(jié)點，為空時，將非空表的剩余元素直接鏈接在Lc表的最后。Lc){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=Lanext。amp。} //取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移 else if(padatapbdata) {pcnext=pb。pc=pa。pb =q。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。[算法描述]void MergeList(LinkListamp。 pb=Lbnext。 pb=pbnext。 pa=panext。 Lcnext = q。[題目分析]只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中,合并后的新表使用頭指針Lc指向。 La, LinkListamp。 pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點Lc=pc=La。 { pcnext=pa。pb=pbnext。 delete u。 }}while(pa) {u=pa。 pb=pbnext。delete Lb。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。 Lb,int *n）{∥差集的結(jié)果存儲于單鏈表La中，*n是結(jié)果集合中元素個數(shù)，調(diào)用時為0pa=Lanext。amp。} ∥ A鏈表中當(dāng)前結(jié)點指針后移else if（padataqdata）q=qnext。 delete u。[算法描述]void DisCompose(LinkedList A){ B=A。 ∥C初始化為空表 p=Anext。 }∥將小于0的結(jié)點鏈入B表,前插法 else {pnext=Cnext。 }}（6）設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。 //假定第一個結(jié)點中數(shù)據(jù)具有最大值 p=Lnextnext。（7）設(shè)計一個算法，通過遍歷一趟，將鏈表中所有結(jié)點的鏈接方向逆轉(zhuǎn)，仍利用原表的存儲空間。 Lnext=NULL。 // *p插入在頭結(jié)點之后 p = q。L, int mink, int maxk) { p=Lnext。 p=pnext。 // 查找第一個值 ≥maxk的結(jié)點 q=prenext。 q=s。{q=pllink； qllinkrlink=p； ∥p的前驅(qū)的前驅(qū)之后繼為p pllink=qllink； ∥p的前驅(qū)指向其前驅(qū)的前驅(qū)。[題目分析] 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。{i=1；j=n；∥設(shè)置數(shù)組低、高端指針（下標(biāo)）。 if（ij）while（ij amp。（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（ ）。（4）鏈?zhǔn)綏＝Y(jié)點為：(data,link)，并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作（ ）。top=toplink； D．x=toplink；答案：A解釋：x=topdata將結(jié)點的值保存到x中，top=toplink棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。 //n大于等于0A． C． n（ ）中有所應(yīng)用。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。（9）若一個棧以向量V[1..n]存儲，初始棧頂指針top設(shè)為n+1，則元素x進棧的正確操作是( )。 top++。 top。（11）用鏈接方式存儲的隊列，在進行刪除運算時（?。?。（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（?。?。（15）一個遞歸算法必須包括（　）。試編寫雙棧初始化，判斷棧空、棧滿、進棧和出棧等算法的函數(shù)。 //棧最大可容納元素個數(shù)}DblStack[題目分析]兩棧共享向量空間，將兩棧棧底設(shè)在向量兩端，初始時，左棧頂指針為1，右棧頂為m。棧初始化intreturn入棧操作：intx)∥i為棧號，i=0表示左棧，i=1為右棧，x是入棧元素。return(0)。case}}∥push(3)退棧成功時返回退棧元素∥否則返回1{if(i0 || i1){cout“棧號輸入錯誤”endl；exit(0)。if([0]==1) {cout“?？铡眅ndl；return（1）；}elseif([1]==m { cout“棧空”endl。return([[1]++])。}∥switch{return}[算法討論]試寫一個算法判定給定的字符向量是否為回文。在出棧元素與串中字符比較不等時，結(jié)論字符序列不是回文。}SeqStack。InitStack( amp。 ilen/2。s)){// 每彈出一個字符與相應(yīng)字符比較temp=Pop (amp。// 不等則返回0else i++。算法應(yīng)對異常情況（入棧滿等）給出相應(yīng)的信息。 for(i=1。 //從鍵盤讀入整數(shù)序列。}else s[++top]=x。exit(0)。規(guī)定：逆波蘭表達式的長度不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔,操作符只可能有+、*、/四種運算。這個過程一直進行到讀出表達式結(jié)束符$，這時OPND棧中只有一個數(shù)，就是結(jié)果。init(OPND)。cinx。x=’9’)||x==’.’) //拼數(shù)if(x!=’.’) //處理整數(shù){num=num*10+（ord(x)ord(‘0’)）。 cinx。scale=scale*10。//數(shù)壓入棧，下個數(shù)初始化 case x=‘ ’:break。 case x=‘’:x1=pop(OPND)。 case x=‘*’:push(OPND,pop(OPND)*pop(OPND))。push(OPND,x2/x1)。//讀入表達式中下一個字符。算法中拼數(shù)部分是核心。當(dāng)讀到小數(shù)點，認(rèn)為數(shù)的整數(shù)部分已完，要接著處理小數(shù)部分。（5）假設(shè)以I和O分別表示入棧和出棧操作。答案：①A和D是合法序列，B和C 是非法序列。 {i=0。 while(A[i]!=‘\0’) //當(dāng)未到字符數(shù)組尾就作。 case‘O’: k++。} if(j!=k) {cout“序列非法”endl；return(false)。整個序列（即讀到字符數(shù)組中字符串的結(jié)束標(biāo)記‘\0’），入棧次數(shù)必須等于出棧次數(shù)（題目中要求棧的初態(tài)和終態(tài)都為空），否則視為非法序列。struct queuenode *next。 //只設(shè)一個指向隊尾元素的指針(1) 置空隊void InitQueue( LinkQueue *Q){ //置空隊：就是使頭結(jié)點成為隊尾元素　QueueNode *s。delete s。}(3) 入隊void EnQueue( LinkQueue *Q, Datatype x){ //入隊。//初始化新結(jié)點并鏈入Qrearnext=p。QueueNode *p。 //保存結(jié)點中數(shù)據(jù)if (p==Qrear){//當(dāng)隊列中只有一個結(jié)點時，p結(jié)點出隊后，要將隊尾指針指向頭結(jié)點　Qrear = Qrearnext。//摘下結(jié)點pdelete p。[算法描述](1)初始化SeQueue QueueInit(SeQueue Q){//初始化隊列==0。}(2)入隊SeQueue QueueIn(SeQueue Q,int e){//入隊列if((==1) amp。{=(+1) % m。Q。e=[]。}(8）如果允許在循環(huán)隊列的兩端都可以進行插入和刪除操作。定義front=rear時為隊空，(rear+1)%m=front 為隊滿。}cycqueue。}=(+M)%M。}//從隊尾刪除算法結(jié)束void enqueue (cycqueue Q, elemtp x)// Q是順序存儲的循環(huán)隊列，本算法實現(xiàn)“從隊頭插入”元素x。 //x 入隊列=(+M)%M。② 寫出計算Ack(m,n)的非遞歸算法。n==0) return(Ack(m1,1))。for(j=0。im。j++)akm[i][j]=akm[i1][akm[i][j1]]。 else { int max=GetMax(pnext)。 }}③double GetAverage(LinkList p , int n){ if(!pnext) return pdata。 A．可以順序存儲 B．?dāng)?shù)據(jù)元素是一個字符 C．可以鏈?zhǔn)酱鎯? D．?dāng)?shù)據(jù)元素可以是多個字符若 答案：B（2）串下面關(guān)于串的的敘述中，（ ）是不正確的？ A．串是字符的有限序列 B．空串是由空格構(gòu)成的串C．模式匹配是串的一種重要運算 D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯Υ鸢福築解釋：空格常常是串的字符集合中的一個元素，有一個或多個空格組成的串成為空格串，零個字符的串成為空串，其長度為零。A．串中所含不同字母的個數(shù) B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù) D．串中所含非空格字符的個數(shù)答案：B解釋：串中字符的數(shù)目稱為串的長度。A．BA+141 B．BA+180 C．BA+222 D．BA+225答案：B解釋：以列序為主，則LOC[5,8]=[（81）*8+（51）]*3+BA=BA+180。若A按行先存儲，元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素（ ）的起始地址相同。（11）設(shè)二維數(shù)組A[1.. m，1.. n]（即m行n列）按行存儲在數(shù)組B[1.. m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（ ）。A．55 B．45 C．36 D．16答案：B解釋：共有5*3*3=45個元素。A．a(chǎn) B．( ) C．(a,b,c,d) D．(b,c,d)答案：C、B解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，((a,b,c,d))的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個廣義表，((a,b,c,d))的表尾為空表( )。2．應(yīng)用題 （1）已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。② 利用KMP(改進的nextval)算法，每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素A[i,j]的長度均為32個二進位,行下標(biāo)從1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。[題目分析] 由于字母共26個，加上數(shù)字符號10個共36個，所以設(shè)一長36的整型數(shù)組，前10個分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。｛int i，num[36]；char ch；　for（i＝0；i36；i++）num[i]＝０；// 初始化　while（（ch＝getchar（））!=‘’） //‘’表示輸入字符串結(jié)束?！or（i＝10；i36；i++）// 求出字母字符的個數(shù) cout“字母字符”i+55 “的個數(shù)=”num[i]endl。{char ch。.39。 A[i++] = ch。函數(shù)void insert(char*s,char*t,int pos)將字符串t插入到字符串s中，插入位置為pos。對插入位置pos要驗證其合法性，小于1或大于串s的長度均為非法，因題目假設(shè)給字符串s的空間足夠大，故對插入不必判溢出。 //p，q分別為字符串s和t的工作指針 if(pos1) {cout“pos參數(shù)位置非法”endl。ipos) {p++。/039。/039。 while(*q!= 39。 } //查找字符串t的長度x，循環(huán)結(jié)束時q指向39。j){*(p+x)=*p。 //指針q回退到串t的最后一個字符 for(j