第三章棧、隊列和數(shù)組一、名詞解釋：1.棧、棧頂、棧底、棧頂元素、空棧 2.順序棧3.鏈棧4.遞歸5.隊列、隊尾、隊頭6.順序隊循環(huán)隊8.隊滿9.鏈隊10.隨機存儲結(jié)構(gòu) 11.特殊矩陣12.稀疏矩陣13.對稱方陣14.上(下)三角矩陣二、填空題：棧修改的原則是 或稱 ，因此，棧又稱為 線性表。在棧頂進行插入運算，被稱為 或 ，在棧頂進行刪除運算，被稱為 TOC\o"1-5"\h\z或 。棧的基本運算至少應包括 、 、 、 、 五種。對于順序棧，若棧頂下標值top=0,此時，如果作退棧運算，則產(chǎn)生“ ”。對于順序棧而言，在棧滿狀態(tài)下，如果此時在作進棧運算，則會發(fā)生“ ”。一般地，棧和線性表類似有兩種實現(xiàn)方法，即 實現(xiàn)和 實現(xiàn)。top=0表示 ，此時作退棧運算，則產(chǎn)生“ ”；top=sqstack_maxsize-1表示 ，此時作進棧運算，則產(chǎn)生“ ”。 處用適當?shù)木渥佑枰蕴畛洹?處用適當?shù)恼Z句予以填充。 處用適當?shù)木渥佑枰蕴畛洹?處用適當?shù)恼Z句予以填充。“棧滿”);return(0);}intInitStack(SqStackTp*sq){ ;return(1);}以下運算實現(xiàn)在順序棧上的進棧，請在IntPush(SqStackTp*sq,DataTypex){if(sp->top==sqstack_maxsize-1}{error(else{ : =x;return(1);}}以下運算實現(xiàn)在順序棧上的退棧，請在 用適當句子予以填充。IntPop(SqStackTp*sq,DataType*x){if(sp->top==0){error(“下溢”);return(0);}else{*x= ; ;return(1);}}以下運算實現(xiàn)在順序棧上判棧空，請在 處用適當句子予以填充。IntEmptyStack(SqStackTp*sq){if( )return(1);elsereturn(0);}以下運算實現(xiàn)在順序棧上取棧頂元素，請在 處用適當句子予以填I(lǐng)ntGetTop(SqStackTp*sq,DataType*x){if( )return(0);else{*x= ;return(1);}}以下運算實現(xiàn)在鏈棧上的初始化，請在 處用請適當句子予以填充。VoidInitStacl(LstackTp*ls){ ;}'以下運算實現(xiàn)在鏈棧上的進棧，請在處用請適當句子予以填充。VoidPush(LStackTp*ls,DataTypex){LstackTp*p;p=malloc(sizeof(LstackTp)); p->next=ls;} 處用請適當句子予以填充。．以下運算實現(xiàn)在鏈棧上的退棧，請在 處用請適當句子予以填充。IntPop(LstackTp*ls,DataType*x){LstackTp*p;if(ls!=NULL){p=ls;*x=;ls=ls->next; return(1) ；}elsereturn(0);}以下運算實現(xiàn)在鏈棧上讀棧頂元素，請在 處用請適當句子予以填充。IntGetTop(LstackTp*ls,DataType*x){if(ls!=NULL){ ;return(1);}elsereturn(0);}必須注意，遞歸定義不能是“循環(huán)定義”。為此要求任何遞歸定義必須同時滿足如下條件：①被定義項在定義中的應用(即作為定義項的出現(xiàn))具有;②被定義項在最小“尺度”上的定義不是的。．隊列簡稱 。在隊列中，新插入的結(jié)點只能添加到 被刪除的只能是排在 的結(jié)點。．隊列以線性表為邏輯結(jié)構(gòu)，至少包括 、 、 、 、五種基本運算。．順序隊的出、入隊操作會產(chǎn)生“ ”。．以下運算實現(xiàn)在循環(huán)隊上的初始化，請在 處用適當句子予以填充。VoidInitCycQueue(CycqueueTp*sq){ ;sq->rear=0;}以下運算實現(xiàn)在循環(huán)隊上的入隊列，請在 處用請適當句子予以填充。IntEnCycQueue(CycquereTp*sq,DataTypex)

{if((sq->rear+1)%maxsize== ){error(“隊滿”);return(0);else{ ; ;return(1);}以下運算實現(xiàn)在循環(huán)隊上的出隊列，請在 處用適當句子予以填充。IntOutCycQueue(CycquereTp*sq,DataType*x){if(sq->front== ){error(“隊空”);return(0)；}else{ ; ;return(1);}}以下運算實現(xiàn)在循環(huán)隊上判隊空，請在 處用適當句子予以填充。IntEmptyCycQueue(CycqueueTpsq){if( )return(1);else return(0);}以下運算實現(xiàn)在循環(huán)隊上取隊頭，請在 處用適當句子予以填充。IntGetHead(CycqueueTpsq,DataType*x){if== return(0);else{*x=[ ];return(1);}鏈隊在一定范圍內(nèi)不會出現(xiàn) 的情況。當 ==試，隊中無元素，此時 處用適當句子予以填充。 處用適當句子予以填充。26．以下運算實現(xiàn)在鏈隊上的初始化，請在 處用適當句子予以填充。 處用適當句子予以填充。voidInitQueue(QueptrTp*lp){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp)) ；lq->rear=p;(lq->front)->next= ;}以下運算實現(xiàn)在鏈隊上的入隊列，請在VoidEnQueue(QueptrTp*lq,DataTypex){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp)); =x;p->next=NULL;(lq->rear)->next= ; ;28.以下運算實現(xiàn)在鏈隊上的出隊列，請在處用適當句子予以填充。intOutQueue(QuetrTp*lq,DataType*x){LqueueTp*s;if(lq->front==lq->rear){erroe( “隊空”);return(0);}else{s=(lq->front)->next; =s->data;(lq->front)->next= ;if(s->next==NULL)lq->rear=lq->front;free(s);return⑴；}}29.以下運算實現(xiàn)在鏈隊上判隊空，請在處用適當句子予以填充intEmptyQueue(QueptrTp*lq){if()return(1);elsereturn(0);}30.以下運算實現(xiàn)在鏈隊上讀隊頭元素，請在處用適當句子予以填充。IntGetHead(QueptrTplq,DataType*x){LqueueTp*p;if==return(0);else{; =p->data;return⑴；}}31.一般地，一個n維數(shù)組可視為其數(shù)據(jù)元素為維數(shù)組的線性表。數(shù)組通常只有和兩種基本運算。32,通常采用存儲結(jié)構(gòu)來存放數(shù)組 。對二維數(shù)組可有兩種存儲方法：一種是以為主序的存儲方式，另一種是以為主序的存儲方式。C語言數(shù)組用的是以序為主序的存儲方法；FORTRAN^言用白^是以序為主序的存儲方法.需要壓縮存儲的矩陣可分為矩陣和矩陣兩種。.對稱方陣中有近半的元素重復， 若為每一對元素只分配一個存儲空間 ，則可將n2個元素壓縮存儲到個元素的存儲空間中。.假設(shè)以一維數(shù)組M(1:n(n+1)/2)作為n階對稱矩陣A的存儲結(jié)構(gòu)，以行序為主序存儲其下三角(包括對角線)中的元素，數(shù)組 M和矩陣A間對應的關(guān)系為。.上三角矩陣中，主對角線上的第 t行(1<=t<=n)有個元素，按行優(yōu)先順序存放上三角矩陣中的元素 aj時，aj之前的前i-1行共有個元素，在第i行上，a.是該行的第個元素，M[k]和aj的對應關(guān)系是。當i>j時，aj=c,c存放在M[]中。.下三角矩陣的存儲和對稱矩陣類似。 M[K]和aj的對應關(guān)系是。.基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種， 以下運算按照矩陣A的列序來進行轉(zhuǎn)置，請在 處用適當?shù)木渥佑靡蕴畛?。Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b){(*b).mu=;(*b).nu=;(*b).tu=;if{q=1;for(col=1; ;col++)for(p=1;p<=;p++)if( ==col){(*b).data[q].i=[p].j;(*b).data[q].j=[p].i;(*b).data[q].v=[p].v; ;}}．基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下計算按照矩陣 A的三元組的次序進行轉(zhuǎn)置，請在 處用適當?shù)木渥佑靡蕴畛洹ast_Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b){(*b).mu=;(*b).nu=;(*b).tu==;if{for(col=1; ;col++)num[col]=0;for(t=1;t<=a,tu;t++)num[[t].j]++;cpot[1]=1;for(col=2;col<=;col++)cpot[col]= ;for(p=1;p<=;p++){col=[p].j;q=cpot[col];(*b).data[q].i=[p].j;(*b).data[q].j=[p].i;(*b).data[q].v=[p].v; ;}}}．棧稱為 線性表。 ;．隊稱為 線性表。設(shè)一個鏈棧的棧頂指針為ls，棧中結(jié)點的格式為infonext,?？盏臈l件是 ；如果棧不為空，則退棧操作為p=ls; ;ls=ls->next;free(p)。.設(shè)有二為數(shù)組intM[10][20](注：m為0...10,n為0…20), 每個元素(整數(shù))棧兩個存儲單元，數(shù)組的起始地址為2000，元素M[5][10]的存儲位置為 ，M[8][19]的存儲值為 。．在具有n個單元的循環(huán)隊列中，隊滿時共有 個元素。． 可以作為實現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。．數(shù)組M中每個元素的長度是 3個字節(jié)，行下標i從1到8，列下標j從1到0，從首的址EA開始連續(xù)存放在存儲其中。若按行方式存放，元素 M[8][5]的起始地址為TOC\o"1-5"\h\z ；若按列優(yōu)先方式存放，元素 M[8][5]的地址為 。．對帶有頭結(jié)點的列隊列l(wèi)q,判定隊列中只有一個數(shù)據(jù)元素的條件是 。．二維數(shù)組M的成員是6個字符(每個字符棧一個存儲單元)組成的串，行下標 i的范圍從0到8,列下標j的范圍從1到10,則存放M至少需要個字節(jié)；M的第8列和第5行共占個字節(jié)；若M按行方式存儲，元素M[8][5]的起始地址與當 M按列優(yōu)先方式存儲時的 元素的起始地址一致。三、單項選擇題．在以下棧的基本運算中，不是加工型運算的是 ( )①lnitStack(S)②Push(S,X)③Pop(S) ④empty(S).以下說法正確的是 ()①因鏈棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況②因順序棧本身沒有容量限制,故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況③對于鏈棧而言,在棧滿狀態(tài)下 ,如果此時再作進棧運算，則會發(fā)生“上溢”④對于順序棧而言在棧滿狀態(tài)下如果此時再作迸棧運算，則會發(fā)生“下溢”．在以下隊列的基本運算中，不是加工型運算的是 ( )①InitQueue(Q)②EnQueue(Q,X)③OutQueu(Q,X)④GetHead(Q,x)4.順序隊列的人隊操作應為()①=+1 []=x[]=x =+1=+1)%maxsize;[sqrear]=x5.循環(huán)隊列的人隊操作應為[]=x=+1)%maxsize()①二+1[]=x=+1)%maxsize[]=x[]=x=+1[]=x=+1)%maxsize順序隊列的出隊操作為()①=+1)%maxsize②=+1③=+1)%maxsize④=+1循環(huán)隊列的出隊操作為()①=+1)%maxsize②=+1③=+)%maxsize④=+1循環(huán)隊列的隊滿條件為()+1)%mazsize==+1)%maxsize;+1%maxsize==+1sq.(rear+1)%maxsize====循環(huán)隊列的隊空條件為()①+1)%maxsize==+1)%maxsize②+)%maxsize==+1③+1)%maxsize==④==數(shù)組的數(shù)據(jù)元素類型 DataType可根據(jù)實際需要而定義。以下說法完全正確的是 ()①數(shù)組的讀運算可以讀取一個數(shù)據(jù)元素整體 ,寫運算只能修改一個數(shù)據(jù)元素的一部分②數(shù)組的讀、寫運算可以讀取或修改一個數(shù)據(jù)元素的一部分或一個整體③數(shù)組的讀、寫運算只能讀取或修改一個數(shù)據(jù)元素的一部分④數(shù)組的讀、寫運算只能讀取或修改一個數(shù)據(jù)元素整體對于以行序為主序的存儲結(jié)構(gòu)來說，在數(shù)組A[ci???di,C2???d2]中，cl和di分別為數(shù)組A的第一個下標的上、下界， C2…d2分別為第二各下標的上、下界，每個數(shù)據(jù)元素占 K個存儲單元，二維數(shù)組中任一元素a[i,j]的存儲位置可由()式確定.①Loc[i,j]=[(d 2-c2+1)(i-c 1)+(j-c2)]*k②Loc[i,j]=loc[c1,c2]+[(d2-c2+1)(i-c 1)+(j-c2)]*k③Loc{i,j}=A[c1,c2]+[(d2-c2+1)(i-c 1)+(j-c2)]*k④Loc[i,j]=loc[0,0]+[(d 2-c2+1)(i-c 1)=(j-c 2)]*k12對于C語言的二維數(shù)組 DataTypeA[m][n], 每個數(shù)據(jù)元素占K個存儲單元，二維數(shù)組中任意元素a[i,j]的存儲位置可由()式確定.①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k④Loc[i,j]=[(n+1)*i+j]*k線性表的順序存儲結(jié)構(gòu)是一種()的存儲結(jié)構(gòu) ,線性表的鏈式存儲結(jié)構(gòu)是一種()的存儲結(jié)構(gòu)。①隨機存取 ②順序存儲14．如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作是 ()①必須判別棧是否滿 ②必須判別棧是否空③判別棧元素的類型 ④對棧不做任何操作15對于基于三元組的稀疏矩陣轉(zhuǎn)置的處埋方法以下說法正確的是 ()①按照矩陣 A的列序來進行轉(zhuǎn)置，算法的時間復雜度為 0(nu+tu)②按照A的三元組的次序進行轉(zhuǎn)置，算法的時間復雜度為O(nu*tu)③按照矩陣 A的列序來進行轉(zhuǎn)置的方法稱快速轉(zhuǎn)置④按照矩陣 A的列序進行轉(zhuǎn)置 ,對于tu<<muxnu才有意義。TOC\o"1-5"\h\z16．稀疏矩陣的壓縮存儲方法是只存儲 ()①非零元素 ②三元祖(i,j,aij) ③aij ④i,j17．基于三元組的稀疏矩陣，對每個非零元素 aij,可以用一個()唯一確定。①非零元素 ②三元組(i,j,aij) ③aij ④i,j18如果以鏈表作為棧的存儲結(jié)構(gòu) ,則退棧操作時 ()①必須判別棧是否滿 ②判別棧元素的類型③必須判別棧是否空 ④隊棧不做任何判別19.設(shè)C語言數(shù)組Data[m+1]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊為指針，則執(zhí)行出隊操作的語句為( )①front=front+1 ②front=(front+1)%m③rear=(rear+1)%m ④front=(front+1)%(m+1).三角矩陣可壓縮存儲到數(shù)組()中。

①M[1:n（n+1）/2+1] ②M[1:n（n+1）/2]③M[n（n+1）/2+1] ④M[n（n+1）/2].設(shè)有一順序棧S,元素Sl,S2,S3,S4,S5,S6依次進棧，如果6個元素出線的順序是 S2,S3,S4,S6,TOC\o"1-5"\h\z,s1,則棧的容量至少應該是 （ ）①2 ②3 ③5 ④6.設(shè)有一順序棧已含 3個元素，如下圖所示，元素 a4正等待進棧。那么下列4個序列中不可能出現(xiàn)的出棧序列是 （ ）01sqa101sqa1a2a32 3 maxsize-1Ttop①a3,a1,a4,a2 ②a3,a2,a4,a1 ③a3,a4,a2,a1 ④a4,a3,a2,a1.向一個棧頂指針為Top的鏈中插入一個s所指結(jié)點時，其操作步驟為 （ ）①Top->next=s ②s->next=Top->next;Top->next=s③s->next=Top;Top=s ④s->next=Top;Top=Top->next24.從棧頂指針為Top的鏈棧中刪除一個結(jié)點， 并將被刪節(jié)點的值保存到 x中，其操作步驟為（）①x=Top->data;Top=Top->next ②Top=Top->next;x=Top->data（3）x=Top;Top=Top->next ④x=Top->dataTOC\o"1-5"\h\z25.在一個鏈隊中，若f,r分別為隊首、隊尾指針，則插入 s所指結(jié)點的操作為（ ）①f->next=c;f=s ②r->next=s;r=s③s->next=r;r=s ④s->next=f;f=s26常對數(shù)組進行的兩種基本操作是 （ ）①建立與刪除②索引與修改 ③查找與修改 ④查找與索引.鏈棧與順序棧相比，有一個比較明顯的優(yōu)點即 （ ）①插入操作更方便 ②通常不會出現(xiàn)棧滿的情況③不會出現(xiàn)?？盏那闆r ④刪除操作更方便.若采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點 （ ）①正確 ②錯誤29。二為數(shù)組M[i,j]的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從。至IJ4,歹U下標j的范圍從。到5。M按行存儲時元素M[3,5]的起始地址與M按列存儲時元素（）的起始地址相同。①M[2,4] ②M[3,4] ③M[3,5] ④M[4,4]TOC\o"1-5"\h\z一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是 （ ）edcba ②decba ③dceab ④abcde.一個隊列的人列序是1,2,3,4,則隊列的輸出系列是 （ ）①4,3,2,1 ②1,2,3,4, ③1,4,3,2 ④3,2,4,1.設(shè)計一個判別表達式中左、右括號是否配對出線的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。①線性標的順序存儲結(jié)構(gòu) ②棧③隊列 ④線性表的鏈式存儲結(jié)構(gòu).若已知一個棧的輸入序列為 1,2,3,…,n,其輸出序列為P、P2、...Pno若p1=n,則P1為②n=i③②n=i③n-i+1④不確定34．以下說法正確的是①順序隊和循環(huán)隊的隊滿和隊空判斷條件是一樣的②?？梢宰鳛閷崿F(xiàn)過程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)③插人和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用④在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向?qū)嶋H的隊尾元素，隊列為滿的條件 front=rear35.以下說法正確的是①數(shù)組是同類型值的集合②數(shù)組是一組相繼的內(nèi)存單元③數(shù)組是一種復雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，既不是線性的，也不是樹形的④使用三元組表表示稀疏矩陣的元素，有時并不能節(jié)省存儲空間四、簡答及應用．簡述順序棧的類型定義。．簡述鏈棧的類型定義。．簡述順序隊列、循環(huán)隊列的類型定義。．簡述鏈隊的類型定義。5，寫出基于三元組的稀疏矩陣的類型說明。6．對于循環(huán)隊列，試寫出求隊列長度的算法。7．設(shè)有編號為t，2，3，4的四輛列車。順序進入一個占世界共的展臺，試寫出這四兩列車開出車站的所有可能的順序。8設(shè)有上三角矩陣(aj)n*n,將其上三角元素逐行存于數(shù)組 B(1:m)中(m充分大)，使得B[k]=aij,且k=fl(i)+f2(j)+C。是推導出函數(shù)fl,f2和常數(shù)C(要求fl和f2中不含常數(shù)項)。9．設(shè)有三對角矩陣(aij)n*n,將其三條對角線上的元素逐行存于數(shù)組B(1:3n-2)中，使得B[k]=aij,求：(1)用i、j表示k的下標變換公式；(2)用k表示i、j的下標變換公式 ..閱讀下列程序，寫出程序的運行結(jié)果。#definesqstack_maxsize40typedefstructsqstack{chardata[sqstack_maxsize];inttop;}SqStackTp;main(){SqStackTpsq;inti;charch;InitStack(&sq);For(ch=’A’;ch<=’A’+12;ch++){Push(&sq,ch);printf( “%c”,ch);}printf(“\n”);while(!EmptyStack(sq)){Pop(&sq,&ch);printf( "&c",ch);}printf( "\n");}.閱讀下列算法，寫出其完整的功能。Voidreverse_list(LinkedListTP*head){LstackTPls,p;DataTypex;InitStack(&ls);p=head->next;While(p!=NULL){Push(&ls<p->data);p=p->next;}p=head->next;While(!EmptyStack(&ls)){Pop(&l,&x);p->data=x;p=p-next;}}12,對下列函數(shù)，按照《數(shù)據(jù)結(jié)構(gòu)導論》課本的圖 3-5失利，畫出調(diào)用f(5)是引起的工作棧狀態(tài)變化情況。Intf(intI){if(n==1)return(10);elsereturn(f(I-1)+2);}五、算法設(shè)計1.某汽車輪渡口，過江渡船每次能載 10輛車過江。過江車輛分為客車類和貨車類，上渡船的有如下規(guī)定：同類車先到先上船；且每上4輛客車，才允許上一輛貨車；若等待客車不足4輛，則以火車代替，若無貨車等待允許客車都上船。試寫一算法模擬渡口管理?？梢栽谝粋€數(shù)組中保存兩個棧：一個棧以數(shù)組的第一個單元作為棧底，另一個棧以數(shù)組的最后一個單元作為棧底(如下圖所示) 。設(shè)S是其中一個占，是分別編寫過程push(S,X)(元素X入棧)，出棧pop(S)和取棧頂元素Top(S).題示：設(shè)其中一個棧為 0,另一棧為10 1 2 M-1MM+100棧。底 棧。頂棧1頂.假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列， 并且只設(shè)一個指針指向隊尾元素結(jié)點 (注意不設(shè)頭指針)，試編寫相應的初始化隊列、入隊列和出隊列算法。.假設(shè)以數(shù)組cycque[m](假設(shè)數(shù)組范圍在0..m)存放循環(huán)隊列的元素，同時設(shè)變量 rear和quelen分別指示循環(huán)隊列中隊尾元素位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法。.編寫算法：按行優(yōu)先存儲順序，將稀疏矩陣轉(zhuǎn)換為三元組的表示形式。.稀疏矩陣用三元組的表示形式，試寫一算法實現(xiàn)兩個稀疏矩陣相加， 結(jié)果仍用三元組表示。

.假設(shè)一個算術(shù)表達式中可以包含三中括號：圓括號“ (”和“)”，方括號“[”和“]”以及花括號與“{”和“}”，且這三種括號可按任意的次序嵌套試用，如(...[...{...}...[...]...]...(...[...]...) 。試利用棧的運算編寫判斷給TOC\o"1-5"\h\z定表達式中所含括號是否正確 配對出現(xiàn)的算法(可設(shè)表達式已存入字符型數(shù)組中) 。.已知Ackerman函數(shù)定義如下：n1當m 0時akm(m,n尸akm(m1,1)當m0,n 0時akm(m1,akm(m,n1))當m 0,n 0時試寫出遞歸算法。.設(shè)函數(shù)f(m,n)按下式定義(m,n為)0的整數(shù))mn1當m*n6寸f(m,n)=f(m1,f(m,n1))當m*n0時試寫出計算函數(shù)的遞歸過程。.設(shè)有一個背包可以放入的物品重量為 S,現(xiàn)有n件物品，重量分別為 W1,W2,... ,Wn.問能否從這n件物品中選擇若干件放入此背包， 使得放入的重量之和正好為 S.如果存在一種符合上述要求的選擇，則稱此背包問題有解(或承接為真) ，否則此問題無解(或結(jié)為假)，試用遞歸和非遞歸兩種方法設(shè)計此背包問題的算法。.借助棧(可用棧的基本運算)來實現(xiàn)單鏈表的逆置運算。第3章棧和隊列參考答案一、名詞解釋(略)二、填空題先進后出、后進先出，后進先出，進棧，入棧，退棧，出棧初始化InitStack(S)、進棧Push(S,X),退棧Pop(S),讀棧頂Top(S),判?？誆mpty(S)下溢上溢順序、鏈接?？铡⑾乱?、棧滿、上溢sq->top=0sq->top++,sq->data[sq->top]sq->data[sq->top],sq->top—10、 sq->top==011、sq->top==0,sq->data[sq->top]12、ls=NULL13、p->data=x,ls=p14、p->data,free(p)15、*x=ls->data16、 更小的“尺度”、遞歸17、隊、隊尾、隊頭

18、隊列初始化InitQueue(Q)、入隊列EnQueue(Q,X)、出隊OutQueue(Q,X)、判隊列空EmptyQueue(Q)、讀隊頭ead(Q,x)19、假溢出20、sq->front=021、sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x22、sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x=sq->data[sq->rear]23、=24、,+1)%maxsize25、隊滿、隊空26、lq->front=p,NULL27、p->data,p,lq->rear=p28、*x,s->next29、 ==30、p=>next,*x31、先進后出(后進先出)32、先進先出(后進后出)33、ls==NULL,*x=p->info34、n-135、棧36、lq->front->next==lq->rear三、單項選擇題1、④2、①3、④4、①5、③6、②7、①8、③9、④10、①②11、②12、③13、④14、②15、①16、③17、①18、②19、③20、②21、③22、②23、②24、③25、②四、簡答及應用1、順序棧類型定義如下：#definesqstackmaxsize順序棧的容量typedefstructsqstack{DataTypedata[sqstackmaxsize];inttop}SqStackTp它有兩個域：data和top。Data為一個一維數(shù)組. 用于存儲棧中元素. DataType為棧元素的數(shù)據(jù)類型。Top為int型.它的實際取值范圍為 0?sqstack_maxsize—1。2、鏈棧的類型定義如下：typedefstuctnode{DataTypedata;structnode*next;}LstackTp;單鏈表的第一個結(jié)點就是鏈棧棧頂結(jié)點，鏈棧由棧頂指針惟一確定。棧中的其它結(jié)點通過它們的next域鏈接起來不。棧底結(jié)點的 next域為NULL3、順序隊列的類型定義如下：#definemaxsize順序棧的容量typedefstructsqqueue{DataTypedata[maxsize];intfornt,rear}SqQueueTpSqQueueTpsq;該類型變量有三個域：data,front,rear。其中data存儲隊中元素的一維數(shù)組。隊頭指針front和隊尾指針rear定義為整型變量，實際取值范圍為 0~maxsize—1。循環(huán)隊列的類型定義如下：#definemaxsize 循環(huán)隊的容量typedefstructcycqueue{DataTypedata[maxsize]Intfront,rear}CycqueueTp;CycqueueTpsq;4、typedefstructlinkedqueue{DataTypedata;structlinkedqueue*next;}LqueueTp;typedefstructqueueptr{LqueueTp*front,*rear;}QueptrTp;QueptrTpIq;5、#definemaxnum 非零元素的容量typedefstructnode{inti,j; /*非零元素所在的行號、歹1號 */DataTypev;/*非零元素的值*/}NODE;typedefstructspmatrix{intmu.nu.tu: /*行數(shù)、列數(shù)、三E零元素的個數(shù)*/NODEdata[maxnum+1];/* 這里假，定三元組的下標的起始值為 1*/

}SpMatrixTp6、intlength(CycqueueTpsq){len=、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、24318、運行結(jié)果：ABCDEFGHIJKLMMLKJIHGFEDCBA9、借助棧將一個帶頭結(jié)點的單鏈表倒置。10Top->Top->Top->Top->Top->Top->Jr2r'''2r3r''3r''3r4r，4r，4r，4r5r5r5r5r5r調(diào)用f(5)前調(diào)用f(5)前調(diào)用f(4)前 調(diào)用f(3)前 調(diào)用f(2)前 調(diào)用f⑴前Top->Top->Top->Top->Top->2r'''3r''3r''4r，4r，4r，5r_5匚5r5r返回f(1)后 返回f(2)后返回f(3)后 返回f(4)后返回f(5)直五、算法設(shè)計.本程序中.將客車類定義一個隊 KE貨車類定義一個隊 HE過江渡船定義成一個棧 DG棧采用順序存儲結(jié)構(gòu).隊采用鏈式存儲結(jié)構(gòu)。#definesqstackmaxsize10typedefstructsqstack{DataTypedata[sqstack_maxsize]; inttop;}SqStackTp;typedefstructlinked_queue _{DataType_data;_—struct_linked=queue_*next;_

}LqueueTp;typedefstructqueueptr{LqueueTp*front,*rear;}QueptrTp;intInitStack(SqStackTp*sq){sq->top=0;return(1);}voidInitQueue(QueptrTp*lp){LqueueTp*p;p=(LqueueTp*)malloc(sizeof(LqueueTp));lq->front=p;lq->rear=p;(lq->front)->next=NULL;}intQutQueue(QueptrTp*lp,DataType*x){LqueueTp*s;if(lq->front==lq->rear){error(“隊空”);return(0);}else{s=(lq->front)->nest;*x=s->data;(lq->front)->next=s->next;if(s->next==NULL)lq->rear=llq->front;free(s);return⑴；—}—}_intEmptyQueue(QueptrTplq){if==return(1);return(0);}intPush(SqStackTp*sq,DataTypex){if(sq->top==sqstackmaxsize-q){return(0);}else{sq