【正文】 e pop(stk S,intreturn(1)。1: [[1]]=x。break。return(1)。0: [++[0]]=x。}switch(i)}if([1][0]==1) {cout“棧已滿”endl。入棧成功返回1，失敗返回0{if(i0||i1){ cout“棧號(hào)輸入不對(duì)”endl。i,intpush(stk S//初始化成功}(2)1。[1]=m。Init()[算法描述](1)兩棧頂指針相鄰時(shí)為棧滿。 //棧數(shù)組 int m。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef struct{int top[2],bot[2]。兩個(gè)棧均從兩端向中間增長。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分答案：B2．算法設(shè)計(jì)題（1）將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn)答案：C解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。 A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rearl)%n==front答案：B解釋：最大容量為n的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n==front，隊(duì)空條件是rear==front。A. rear=rear+1 B. rear=(rear+1)%(m1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解釋：數(shù)組A[0..m]中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。A．線性表的順序存儲(chǔ)結(jié)構(gòu) B．隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧答案：D解釋：利用棧的后進(jìn)先出原則。答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V[1..n]中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。 D．V[top]=x。C．top。 B．V[top]=x。A．top++。A．2 B．3 C．4 D． 6答案：B解釋：元素出隊(duì)的序列是eeeee5和e1，可知元素入隊(duì)的序列是eeeee5和e1，即元素出棧的序列也是eeeee5和e1，而元素eeeee5和e6依次進(jìn)入棧，易知棧S中最多同時(shí)存在3個(gè)元素，故棧S的容量至少為3。A．隊(duì)列 B．棧 C． 線性表 D．有序表答案：A解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。A．遞歸調(diào)用 B．函數(shù)調(diào)用 C．表達(dá)式求值 D．前三個(gè)選項(xiàng)都有答案：D解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。（6）棧在 D． n+2答案：A解釋：特殊值法。n1n+1 else return n*fact(n1)。 if(n=0) return 1。 int fact(int n) {（5）設(shè)有一個(gè)遞歸算法如下x=toplink； C．x=top。A．x=topdata。A．rf B．(n+fr)%n C．n+rf D．（n+rf)%n答案：D解釋：對(duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長度，而對(duì)于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+rf)%n。A．i B．ni C．ni+1 D．不確定答案：C解釋：棧是后進(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，…，n，而輸出序列的第一個(gè)元素為n，說明1，2，3，…，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n1，…，pi=ni+1。A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1答案：C解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。amp。 A[i]!=item）i++； ∥若值不為item，左移指針。 while（ij） {while（ij amp。[算法描述]void Delete（ElemType A[ ]，int n）∥A是有n個(gè)元素的一維數(shù)組，本算法刪除A中所有值為item的元素。本題要求刪除線性表中所有值為item的數(shù)據(jù)元素，并未要求元素間的相對(duì)位置不變。（10）已知長度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)間復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。 qrlink=prlink； ∥p的前驅(qū)的后繼為p的后繼。[算法描述]void Exchange（LinkedList p）∥p是雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，本算法將p所指結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)交換。 } // 釋放結(jié)點(diǎn)空間 }//if}（9）已知p指向雙向循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)結(jié)構(gòu)為data、prior、next三個(gè)域，寫出算法change(p),交換p所指向的結(jié)點(diǎn)和它的前綴結(jié)點(diǎn)的順序。 delete q。 prenext=p。 pdatamaxk) p=pnext。 } //查找第一個(gè)值mink的結(jié)點(diǎn) if (p) {while (p amp。 pdata=mink) { pre=p。 //首元結(jié)點(diǎn) while (p amp。[算法描述]void delete(LinkList amp。 }}（8）設(shè)計(jì)一個(gè)算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個(gè)參數(shù)，其值可以和表中的元素相同，也可以不同 ）。 Lnext=p。 while ( p) { q=pnext。L) {// 逆置帶頭結(jié)點(diǎn)的單鏈表 L p=Lnext。[題目分析]從首元結(jié)點(diǎn)開始，逐個(gè)地把鏈表L的當(dāng)前結(jié)點(diǎn)p插入新的鏈表頭部。//遍歷鏈表 } return pmaxdata。 while(p != NULL ){//如果下一個(gè)結(jié)點(diǎn)存在 if(pdata pmaxdata) pmax=p。 pmax=Lnext。[題目分析]假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值，依次與下一個(gè)元素比較，若其小于下一個(gè)元素，則設(shè)其下一個(gè)元素為最大值，反復(fù)進(jìn)行比較，直到遍歷完該鏈表。∥p指向新的待處理結(jié)點(diǎn)。 Cnext=p。 Bnext=p。 ∥p為工作指針 while(p!= NULL) { r=pnext?！螢镃申請(qǐng)結(jié)點(diǎn)空間 Cnext=NULL。Bnext= NULL。從A表的第一個(gè)結(jié)點(diǎn)開始，依次取其每個(gè)結(jié)點(diǎn)p，判斷結(jié)點(diǎn)p的值是否小于0，利用前插法，將小于0的結(jié)點(diǎn)插入B表,大于等于0的結(jié)點(diǎn)插入C表。} ∥刪除結(jié)點(diǎn)}}（5）設(shè)計(jì)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點(diǎn)為A表中值小于零的結(jié)點(diǎn)，而C表的結(jié)點(diǎn)為A表中值大于零的結(jié)點(diǎn)（鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點(diǎn)）。 pa=panext。 ∥B鏈表中當(dāng)前結(jié)點(diǎn)指針后移 else {prenext=panext。*n++。pb）{if（padataqdata）{pre=pa。 ∥pre為La中pa所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針 while（paamp。 pb=Lbnext。 La, LinkListamp。當(dāng)鏈表La和Lb有一個(gè)為空時(shí)，依次刪除另一個(gè)非空表中的所有元素。[題目分析]求兩個(gè)集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點(diǎn),所以要保存待刪除結(jié)點(diǎn)的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點(diǎn)。 //釋放Lb的頭結(jié)點(diǎn) }（4）已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列?！沃面湵砦矘?biāo)記。 delete u。}∥ 釋放結(jié)點(diǎn)空間while(pb) {u=pb。 pa=panext。 delete u。 }else { u=pb。 pa=panext。 Delete u。 u=pb。 pc=pa。pb){ if(padata==pbdata)∥交集并入結(jié)果表中。 //用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(paamp。pb=Lbnext。 Lb, LinkListamp。[算法描述]void Mix(LinkListamp。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，如果兩個(gè)表中相等的元素時(shí)，摘取La表中的元素，刪除Lb表中的元素；如果其中一個(gè)表中的元素較小時(shí)，刪除此表中較小的元素，此表的工作指針后移。請(qǐng)?jiān)O(shè)計(jì)算法求出A與B的交集，并存放于A鏈表中。 //將q指向的結(jié)點(diǎn)插在Lc 表的表頭結(jié)點(diǎn)之后 } delete Lb。}//取較小者Lb中的元素，用q指向pb，pb指針后移 qnext = Lcnext。}//取較小者（包括相等）La中的元素，用q指向pa，pa指針后移 else {q=pb。} //Lb表為空，用q指向pa，pa指針后移 else if(padata=pbdata) {q=pa。}//La表為空，用q指向pb，pb指針后移 else if(!pb) {q=pa。 while(pa||pb ){//只要存在一個(gè)非空表，用q指向待摘取的元素 if(!pa) {q=pb。 //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) Lc=pc=La。 Lc, ) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=Lanext。 La, LinkListamp。當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí)，將非空表的剩余元素依次摘取，鏈接在Lc表的表頭結(jié)點(diǎn)之后。表中允許有重復(fù)的數(shù)據(jù)。 //釋放Lb的頭結(jié)點(diǎn)} （2）將兩個(gè)非遞減的有序鏈表合并為一個(gè)非遞增的有序鏈表。} } pcnext=pa?pa:pb。delete pb 。pa=panext。} //取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移 else //相等時(shí)取La中的元素，刪除Lb中的元素{pcnext=pa。 pc=pb。pa=panext。 pb){if(padatapbdata){pcnext=pa。 //用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn) while(pa amp。 pb=Lbnext。Lb,LinkList amp。[算法描述]void MergeList(LinkList amp。如果兩個(gè)表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。表中不允許有重復(fù)的數(shù)據(jù)。答案：C2．算法設(shè)計(jì)題（1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。 pnext=q。D．qprior=p。 pnextprior=q。C．qprior=p。 qprior=p。B．pnext=q。 pnextprior=q。A．pnext=q。 pnext=ppriorprior。 pprior=ppriorprior。 pnextprior=p。 ppriornext=pnext。 答案：D (14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。D．snext=pnext。C．snext=pnext。B．(*p).next=s。A．snext=p+1。 A．求表長、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低B．順序存