數(shù)據(jù)結(jié)構(gòu)練習(xí)題棧隊(duì)列和數(shù)組習(xí)題及答案

1、第三章 棧、隊(duì)列和數(shù)組一、名詞解釋：1. 棧、棧頂、棧底、棧頂元素、空棧 2.順序棧 3.鏈棧 4.遞歸 5. 隊(duì)列、隊(duì)尾、隊(duì)頭 6. 順序隊(duì) 7.循環(huán)隊(duì) 8.隊(duì)滿 9.鏈隊(duì) 10.隨機(jī)存儲(chǔ)結(jié)構(gòu) 11.特殊矩陣 12.稀疏矩陣 13.對(duì)稱方陣 14.上(下) 三角矩陣二、填空題：1. 棧修改的原則是 或稱 ，因此，棧又稱為 線性表。在棧頂進(jìn)行插入運(yùn)算， 被稱為 或 ，在棧頂進(jìn)行刪除運(yùn)算， 被稱為 或 。2. 棧的基本運(yùn)算至少應(yīng)包括 、 、五種。3. 對(duì)于順序棧，若棧頂下標(biāo)值 top=0, 此時(shí)，如果作退棧運(yùn)算，則產(chǎn)生“ ”。4. 對(duì)于順序棧而言，在棧滿狀態(tài)下，如果此時(shí)在作進(jìn)棧運(yùn)算，則會(huì)發(fā)生“

2、”。5. 一般地，棧和線性表類似有兩種實(shí)現(xiàn)方法，即 實(shí)現(xiàn)和 實(shí)現(xiàn)。6. top=0 表示 ，此時(shí)作退棧運(yùn)算， 則產(chǎn)生“ ”；top=sqstack_maxsize-1表示 ，此時(shí)作進(jìn)棧運(yùn)算，則產(chǎn)生“ ”。7. 以下運(yùn)算實(shí)現(xiàn)在順序棧上的初始化，請(qǐng)?jiān)?int InitStack(SqStackTp *sq) ;return(1);8. 以下運(yùn)算實(shí)現(xiàn)在順序棧上的進(jìn)棧，請(qǐng)?jiān)?Int Push(SqStackTp *sq,DataType x) if(sp-top=sqstack_maxsize-1error(else:=x;return(1);處用適當(dāng)?shù)木渥佑枰蕴畛洹Ｌ幱眠m當(dāng)?shù)恼Z(yǔ)句予以填充。“棧滿”

3、);return(0);9. 以下運(yùn)算實(shí)現(xiàn)在順序棧上的退棧，請(qǐng)?jiān)?用適當(dāng)句子予以填充。Int Pop(SqStackTp *sq,DataType *x)if(sp-top=0)error( “下溢” );return(0);else*x=;return(1);10. 以下運(yùn)算實(shí)現(xiàn)在順序棧上判?？?，請(qǐng)?jiān)?處用適當(dāng)句子予以填充。Int EmptyStack(SqStackTp *sq)if() return(1);else return(0);11. 以下運(yùn)算實(shí)現(xiàn)在順序棧上取棧頂元素，請(qǐng)?jiān)?處用適當(dāng)句子予以填充。Int GetTop(SqStackTp *sq,DataType *x)if()

4、return(0);else*x=;return(1);12. 以下運(yùn)算實(shí)現(xiàn)在鏈棧上的初始化， 請(qǐng)?jiān)?處用請(qǐng)適當(dāng)句子予以填充。Void InitStacl(LstackTp *ls) ;13. 以下運(yùn)算實(shí)現(xiàn)在鏈棧上的進(jìn)棧，請(qǐng)?jiān)谔幱谜?qǐng)適當(dāng)句子予以填充。Void Push ( LStackTp *ls,DataType x ) LstackTp *p;p=malloc(sizeof(LstackTp);p-next=ls;14以下運(yùn)算實(shí)現(xiàn)在鏈棧上的退棧，請(qǐng)?jiān)?處用請(qǐng)適當(dāng)句子予以填充。Int Pop(LstackTp *ls,DataType *x) LstackTp *p; if(ls!=NULL

5、) p=ls;ls=ls-next;return(1) ；else return(0); 15. 以下運(yùn)算實(shí)現(xiàn)在鏈棧上讀棧頂元素，請(qǐng)?jiān)?處用請(qǐng)適當(dāng)句子予以填充。Int Get Top(LstackTp *ls,DataType *x) if(ls!=NULL) ;return(1);else return(0);16. 必須注意，遞歸定義不能是“循環(huán)定義” 。為此要求任何遞歸定義必須同時(shí)滿足如下 條件： 被定義項(xiàng)在定義中的應(yīng)用(即作為定義項(xiàng)的出現(xiàn))具有 ； 被定義項(xiàng)在最小“尺度”上的定義不是 的。1 7隊(duì)列簡(jiǎn)稱 。在隊(duì)列中， 新插入的結(jié)點(diǎn)只能添加到 被刪除的只能是排在 的結(jié)點(diǎn)。18隊(duì)列以線性表

6、為邏輯結(jié)構(gòu)，至少包括 、 、 、五種基本運(yùn)算。19順序隊(duì)的出、入隊(duì)操作會(huì)產(chǎn)生“ ”。20以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的初始化，請(qǐng)?jiān)谔幱眠m當(dāng)句子予以填充。Void InitCycQueue(CycqueueTp *sq) ;sq-rear=0;21. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的入隊(duì)列，請(qǐng)?jiān)?處用請(qǐng)適當(dāng)句子予以填充。Int EnCycQueue(CycquereTp *sq,DataType x);return(0);return(1);22. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的出隊(duì)列， 請(qǐng)?jiān)贗nt OutCycQueue(CycquereTp *sq,DataType *x) if(sq-front= )erro

7、r(else 處用適當(dāng)句子予以填充?！瓣?duì)空” );return(0) ； return(1);23. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上判隊(duì)空，請(qǐng)?jiān)贗nt EmptyCycQueue(CycqueueTp sq)if() return(1);else return(0);24. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上取隊(duì)頭，請(qǐng)?jiān)贗nt GetHead(CycqueueTp sq,DataType *x) if= return(0);else *x= ;return(1);25. 鏈隊(duì)在一定范圍內(nèi)不會(huì)出現(xiàn) 處用適當(dāng)句子予以填充。處用適當(dāng)句子予以填充。的情況。當(dāng) =試，隊(duì)中無(wú)元素，此時(shí) if(sq-rear+1)%maxsi

8、ze= error( “隊(duì)滿 else25處用適當(dāng)句子予以填充。處用適當(dāng)句子予以填充。26以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的初始化，請(qǐng)?jiān)趘oid InitQueue(QueptrTp *lp) LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp) ；lq-rear=p;(lq-front)-next=;27. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的入隊(duì)列，請(qǐng)?jiān)赩oid EnQueue(QueptrTp *lq,DataType x) LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp);=x; p-next=NULL;(lq-re

9、ar)-next=;28. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的出隊(duì)列，請(qǐng)?jiān)?處用適當(dāng)句子予以填充。int OutQueue(QuetrTp *lq,DataType *x) LqueueTp *s;if(lq-front=lq-rear)erroe(“隊(duì)空” )；return(0);else s=(lq-fr on t)-n ext;=s-data;(lq-front)-next= ；if(s-n ext=NULL) lq-rear=lq-front;free(s);return(1);29. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上判隊(duì)空，請(qǐng)?jiān)?處用適當(dāng)句子予以填充int EmptyQueue(QueptrTp *lq)

10、if() return；elsereturn(O);30. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上讀隊(duì)頭元素，請(qǐng)?jiān)谔幱眠m當(dāng)句子予以填充。Int GetHead(QueptrTp lq,DataType *x) LqueueTp *p;if= return(O);else;=p-data;return(1);31. 一般地，一個(gè)n維數(shù)組可視為其數(shù)據(jù)元素為 維數(shù)組的線性表。數(shù)組通常只有和兩種基本運(yùn)算。32, 通常采用 存儲(chǔ)結(jié)構(gòu)來(lái)存放數(shù)組。對(duì)二維數(shù)組可有兩種存儲(chǔ)方法：一種是以為主序的存儲(chǔ)方式，另一種是以 為主序的存儲(chǔ)方式。C語(yǔ)言數(shù)組用 的是以序?yàn)橹餍虻拇鎯?chǔ)方法；FORTRAN語(yǔ)言用的是以序?yàn)橹餍虻拇鎯?chǔ)方法33 需要壓

11、縮存儲(chǔ)的矩陣可分為 矩陣和矩陣兩種。34. 對(duì)稱方陣中有近半的元素重復(fù)，若為每一對(duì)元素只分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元素壓縮存儲(chǔ)到 個(gè)元素的存儲(chǔ)空間中。35 .假設(shè)以一維數(shù)組M( 1 : n(n+1)/2 )作為n階對(duì)稱矩陣A的存儲(chǔ)結(jié)構(gòu)，以行序?yàn)橹餍虼鎯?chǔ)其下三角(包括對(duì)角線)中的元素，數(shù)組M和矩陣A間對(duì)應(yīng)的關(guān)系為 。36. 上三角矩陣中，主對(duì)角線上的第t行(1=tj時(shí)，aj =c,c存放在M中。37. 下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似。MK和aj的對(duì)應(yīng)關(guān)系是 。38. 基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下運(yùn)算按照矩陣 A的列序來(lái)進(jìn)行轉(zhuǎn)置，請(qǐng)?jiān)?處用適當(dāng)?shù)木渥佑靡蕴畛?。Trans_Sp

12、armat(SpMatrixTp a,SpMatrixTp *b) (*b).mu=;(*b).nu=;(*b).tu=;if q=1;for(col=1; ;col+)for(p=1;p=;p+) if(=col)(*b).dataq.i=p.j; (*b).dataq.j=p.i; (*b).dataq.v=p.v;39基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下計(jì)算按照矩陣 A 的三元組的次序進(jìn)行轉(zhuǎn)置，請(qǐng)?jiān)?處用適當(dāng)?shù)木渥佑靡蕴畛?。Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) (*b).mu=;(*b).nu=;(*b).tu=;iffo

13、r(col=1;col+) numcol=0;for(t=1;t=a,tu;t+) numt.j+;cpot1=1;for(col=2;col=;col+) cpotcol=;for(p=1;pnext;free（p） 。43 .設(shè)有二為數(shù)組int M1020（ 注：m為O.1O,n 為0.20）,每個(gè)元素（整數(shù)）棧兩個(gè)存儲(chǔ)單元， 數(shù)組的起始地址為 2000，元素 M510 的存儲(chǔ)位置為 ，M819的存儲(chǔ)值為 。44. 在具有 n 個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 個(gè)元素。45. 可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。46 .數(shù)組M中每個(gè)元素的長(zhǎng)度是3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到0

14、，從首的址 EA 開(kāi)始連續(xù)存放在存儲(chǔ)其中。若按行方式存放，元素M85 的起始地址為 ；若按列優(yōu)先方式存放，元素 M85 的地址為 。47 對(duì)帶有頭結(jié)點(diǎn)的列隊(duì)列 lq, 判定隊(duì)列中只有一個(gè)數(shù)據(jù)元素的條件是 。48 二維數(shù)組 M的成員是6個(gè)字符(每個(gè)字符棧一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo) i 的范圍從0到8,列下標(biāo)j的范圍從1到10,則存放M至少需要 個(gè)字節(jié)；M的第8列和第5行共占個(gè)字節(jié)；若M按行方式存儲(chǔ)，元素 M85的起始地址與當(dāng) M按列優(yōu)先方式存儲(chǔ)時(shí)的 元素的起始地址一致。三、單項(xiàng)選擇題1 在以下棧的基本運(yùn)算中,不是加工型運(yùn)算的是() In itStack(S) Push(S,X) Pop(S)

15、 empty(S)2. 以下說(shuō)法正確的是 ( ) 因鏈棧本身沒(méi)有容量限制, 故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況 因順序棧本身沒(méi)有容量限制, 故在用戶內(nèi)存空間的范圍內(nèi)不會(huì)出現(xiàn)棧滿情況 對(duì)于鏈棧而言 , 在棧滿狀態(tài)下 , 如果此時(shí)再作進(jìn)棧運(yùn)算,則會(huì)發(fā)生“上溢” 對(duì)于順序棧而言在棧滿狀態(tài)下如果此時(shí)再作迸棧運(yùn)算，則會(huì)發(fā)生“下溢”。3 在以下隊(duì)列的基本運(yùn)算中，不是加工型運(yùn)算的是() Ini tQueue(Q) En Queue(Q,X) OutQueu(Q,X) GetHead(Q,x)4. 順序隊(duì)列的人隊(duì)操作應(yīng)為( ) =+1=x =x=+1 =+1)% maxsize;=x sqrear=x=

16、+1)% maxsize5. 循環(huán)隊(duì)列的人隊(duì)操作應(yīng)為( ) =+1=x =x=+1 =+1)% maxsize=x =x=+1)% maxsize6. 順序隊(duì)列的出隊(duì)操作為 ( ) =+1)% maxsize =+1 =+1)% maxsize =+17. 循環(huán)隊(duì)列的出隊(duì)操作為 ( ) =+1)% maxsize =+1 =+)% maxsize =+18. 循環(huán)隊(duì)列的隊(duì)滿條件為 ( ) +1) % mazsize =+1) % maxsize; +1 % maxsize =+1 sq.(rear+1) % maxsize = =9. 循環(huán)隊(duì)列的隊(duì)空條件為 ( ) +1) % maxsize

17、=+1) % maxsize +) % maxsize =+1 +1) % maxsize = =10. 數(shù)組的數(shù)據(jù)元素類型 DataType 可根據(jù)實(shí)際需要而定義。以下說(shuō)法完全正確的是 ( ) 數(shù)組的讀運(yùn)算可以讀取一個(gè)數(shù)據(jù)元素整體, 寫(xiě)運(yùn)算只能修改一個(gè)數(shù)據(jù)元素的一部分 數(shù)組的讀、寫(xiě)運(yùn)算可以讀取或修改一個(gè)數(shù)據(jù)元素的一部分或一個(gè)整體 數(shù)組的讀、寫(xiě)運(yùn)算只能讀取或修改一個(gè)數(shù)據(jù)元素的一部分 數(shù)組的讀、寫(xiě)運(yùn)算只能讀取或修改一個(gè)數(shù)據(jù)元素整體11 .對(duì)于以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)來(lái)說(shuō)，在數(shù)組 Aci di, C2 d2中，cl和di分別為 數(shù)組A的第一個(gè)下標(biāo)的上、下界，C2- d2分別為第二各下標(biāo)的上、下界，每

18、個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任一元素 ai,j 的存儲(chǔ)位置可由 ( ) 式確定 . Loci,j=( d2-c 2+i)(i- ci)+(j- c 2)*k Loci,j=locc i, c 2+( d 2- c 2+i)(i- c i)+(j- c 2)*k Loci,j=Ac i, c 2+( d2-c2+i)(i- ci)+(j- c2)*k Loci,j=loc0,0+( d2-c2+i)(i- ci)=(j- c2)*ki2對(duì)于C語(yǔ)言的二維數(shù)組 DataType Amn,每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任意元素 ai,j 的存儲(chǔ)位置可由 Loci,j=Am, n+( n

19、+i)*i+j*k Loci,j=loc0,0+(m+n)*i+j*k Loci,j=loc0,0+( n+i)*i+j*k Loci,j=( n+i)*i+j*ki3. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種 儲(chǔ)結(jié)構(gòu)。 隨機(jī)存取式確定 .) 的存儲(chǔ)結(jié)構(gòu) , 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種)的存 順序存儲(chǔ)14如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作是必須判別棧是否滿必須判別棧是否空判別棧元素的類型對(duì)棧不做任何操作i5 對(duì)于基于三元組的稀疏矩陣轉(zhuǎn)置的處埋方法以下說(shuō)法正確的是 按照矩陣A的列序來(lái)進(jìn)行轉(zhuǎn)置，算法的時(shí)間復(fù)雜度為O(nu+tu) 按照A的三元組的次序進(jìn)行轉(zhuǎn)置，算法的時(shí)間復(fù)雜度為0(nu*tu) 按照矩陣A

20、的列序來(lái)進(jìn)行轉(zhuǎn)置的方法稱快速轉(zhuǎn)置 按照矩陣A的列序進(jìn)行轉(zhuǎn)置，對(duì)于tun ext=s s-n ext=Top;Top=sa1a2a3maxsize-123T top a3,a2,a4,a1 a3,a4,a2,a1Top的鏈中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟為 s-n ext=Top-n ext;Top-n ext=s s-n ext=Top;Top=Top-next并將被刪節(jié)點(diǎn)的值保存到 a4,a3,a2,a1(24. 從棧頂指針為T(mén)op的鏈棧中刪除一個(gè)結(jié)點(diǎn)，( ) x=Top-data;Top=Top-n ext Top=Top-n ext;x=Top-data x=Top;Top=Top-n

21、 ext x=Top-data25. 在一個(gè)鏈隊(duì)中，若f,r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為 f-n ext=c;f=s r-n ext=s;r=s s-n ext=r;r=s s- next=f;f=s26常對(duì)數(shù)組進(jìn)行的兩種基本操作是建立與刪除 索引與修改查找與修改27.鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)即插入操作更方便通常不會(huì)出現(xiàn)棧滿的情況不會(huì)出現(xiàn)?？盏那闆r刪除操作更方便28若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成 了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)(正確錯(cuò)誤29. 二為數(shù)組Mi,j的元素是4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串，行下標(biāo)

22、 范圍從0到4，列下標(biāo)j的范圍從0到5。M按行存儲(chǔ)時(shí)元素 M3,5的起始地址與 儲(chǔ)時(shí)元素() M 2,4x中,其操作步驟為(查找與索引(i的M按列存30. 一個(gè)棧的入棧序列是 e d c b a31. 一個(gè)隊(duì)列的人列序是 4 , 3, 2, 1的起始地址相同。 M3,4 M3,5a,b,c,d,e,貝U棧的不可能的輸出序列是 d e c b a d c e a b1, 2, 3, 4,則隊(duì)列的輸出系列是 1 , 2, 3, 4, 1, 4, 3, M4,4( a b c d e( 3 ， 2， 4，32. 設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出線的算法，采用(線性標(biāo)的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列33.

23、若已知一個(gè)棧的輸入序列為P1為i棧 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1, 2, 3, .,n,其輸出序列為 R、n=i n-i+1不確定)數(shù)據(jù)結(jié)構(gòu)最佳。P2、.P n。若 p1 = n,則34以下說(shuō)法正確的是順序隊(duì)和循環(huán)隊(duì)的隊(duì)滿和隊(duì)空判斷條件是一樣的 ?？梢宰鳛閷?shí)現(xiàn)過(guò)程調(diào)用的一種數(shù)據(jù)結(jié)構(gòu) 插人和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用 在循環(huán)隊(duì)列中， front 指向隊(duì)列中第一個(gè)元素的前一位置， rear 指向?qū)嶋H的隊(duì)尾元素，隊(duì) 列為滿的條件 front=rear35. 以下說(shuō)法正確的是 數(shù)組是同類型值的集合 數(shù)組是一組相繼的內(nèi)存單元 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的

24、關(guān)系，既不是線性的，也不是樹(shù)形的 使用三元組表表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間四、簡(jiǎn)答及應(yīng)用1簡(jiǎn)述順序棧的類型定義。2簡(jiǎn)述鏈棧的類型定義。 3簡(jiǎn)述順序隊(duì)列、循環(huán)隊(duì)列的類型定義。4簡(jiǎn)述鏈隊(duì)的類型定義。5，寫(xiě)出基于三元組的稀疏矩陣的類型說(shuō)明。6對(duì)于循環(huán)隊(duì)列，試寫(xiě)出求隊(duì)列長(zhǎng)度的算法。7設(shè)有編號(hào)為 t， 2， 3， 4 的四輛列車(chē)。順序進(jìn)入一個(gè)占世界共的展臺(tái)，試寫(xiě)出這四兩列車(chē) 開(kāi)出車(chē)站的所有可能的順序。8設(shè)有上三角矩陣(a j)n*n,將其上三角元素逐行存于數(shù)組 B(1:m)中(m充分大)，使得Bk=a耳 且k=fl(i) + f 2(j) + C。是推導(dǎo)出函數(shù)fl,f 2和常數(shù)C(要求f

25、1和f2中不含常數(shù)項(xiàng))。9設(shè)有三對(duì)角矩陣( aij ) n*n, 將其三條對(duì)角線上的元素逐行存于數(shù)組 B(1:3n-2) 中，使得Bk=a ij , 求：(1) 用i、j表示k的下標(biāo)變換公式；( 2)用 k 表示 i 、 j 的下標(biāo)變換公式 .10. 閱讀下列程序，寫(xiě)出程序的運(yùn)行結(jié)果。# defi ne sqstack_maxsize40typedef struct sqstack char datasqstack_maxsize;int top; SqStackTp;main() SqStackTp sq;int i;char ch;InitStack(&sq);For(ch= A;chn

26、ext;While(p!=NULL) Push(&l sdata);p=p-n ext;p=head-n ext;While(! EmptyStack(&l s) Pop(&l,&x); p-data=x;p=p-n ext;12,對(duì)下列函數(shù)，按照數(shù)據(jù)結(jié)構(gòu)導(dǎo)論課本的圖3-5失利，畫(huà)出調(diào)用f(5)是引起的工作棧狀態(tài)變化情況。Int f(int I) if(n=1) return(10);else return(f(I-1)+2);五、算法設(shè)計(jì)1.某汽車(chē)輪渡口，過(guò)江渡船每次能載10輛車(chē)過(guò)江。過(guò)江車(chē)輛分為客車(chē)類和貨車(chē)類，上渡船的有如下規(guī)定：同類車(chē)先到先上船；且每上 4輛客車(chē)，才允許上一輛貨車(chē)；若等待

27、客 車(chē)不足4輛，則以火車(chē)代替，若無(wú)貨車(chē)等待允許客車(chē)都上船。試寫(xiě)一算法模擬渡口管理。可以在一個(gè)數(shù)組中保存兩個(gè)棧：一個(gè)棧以數(shù)組的第一個(gè)單元作為棧底，另一個(gè)棧以 數(shù)組的最后一個(gè)單元作為棧底(如下圖所示)。設(shè)S是其中一個(gè)占，是分別編寫(xiě)過(guò)程push(S,X)(元素X入棧)，出棧pop(S)和取棧頂元素Top(S).題示：設(shè)其中一個(gè)棧為0，另一棧為1。012M-1 M M+10 0棧0底棧0頂 棧1頂3 假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)(注意不設(shè)頭指針)，試編寫(xiě)相應(yīng)的初始化隊(duì)列、入隊(duì)列和出隊(duì)列算法。4 .假設(shè)以數(shù)組cycquem(假設(shè)數(shù)組范圍在 0.m)存放循環(huán)隊(duì)列的元素

28、，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫(xiě)出相應(yīng)的入隊(duì)列和出隊(duì)列的算法。5. 編寫(xiě)算法：按行優(yōu)先存儲(chǔ)順序，將稀疏矩陣轉(zhuǎn)換為三元組的表示形式。6. 稀疏矩陣用三元組的表示形式，試寫(xiě)一算法實(shí)現(xiàn)兩個(gè)稀疏矩陣相加，結(jié)果仍用三元組表示。7假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三中括號(hào)：圓括號(hào)“(”和“)”，方括號(hào)“”和“”以及花括號(hào)與“ ”和“ ”，且這三種括號(hào)可按任意的次序嵌套試用，如( )。試?yán)脳５倪\(yùn)算編寫(xiě)判斷給定表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)的算法(可設(shè)表達(dá)式已存入字符型數(shù)組中)。8 .已知Ackerman函數(shù)定義如下：n 1當(dāng)m0

29、時(shí)akm(m, n)= akm(m 1,1)當(dāng) m 0,n0 時(shí)akm(m 1, akm(m,n 1)當(dāng) m 0, n0時(shí)試寫(xiě)出遞歸算法。9 .設(shè)函數(shù)f(m,n)按下式定義(m,n為)0的整數(shù))m n 1 當(dāng) m* n 0時(shí)f(m, n)=f(m 1,f (m, n 1)當(dāng) m*n 0 時(shí)試寫(xiě)出計(jì)算函數(shù)的遞歸過(guò)程。10. 設(shè)有一個(gè)背包可以放入的物品重量為S,現(xiàn)有n件物品，重量分別為 w,W2,. , Wn.問(wèn)能否從這n件物品中選擇若干件放入此背包，使得放入的重量之和正好為S如果存在一種符合上述要求的選擇，則稱此背包問(wèn)題有解(或承接為真)，否則此問(wèn)題無(wú)解(或結(jié)為假)，試用遞歸和非遞歸兩種方法設(shè)計(jì)

30、此背包問(wèn)題的算法。11. 借助棧(可用棧的基本運(yùn)算)來(lái)實(shí)現(xiàn)單鏈表的逆置運(yùn)算。第3章棧和隊(duì)列參考答案一、名詞解釋(略)二、填空題1、先進(jìn)后出、后進(jìn)先出，后進(jìn)先出，進(jìn)棧，入棧，退棧，出棧2、初始化InitStack(S)、進(jìn)棧Push(S,X), 退棧 Pop(S),讀棧頂 Top(S),判?？?Empty(S)3、下溢4、上溢5、順序、鏈接6、?？?、下溢、棧滿、上溢7、sq-top=08、sq-top+,sq-datasq-top9、sq-datasq-top,sq-top10、sq-top= =011、sq-top= =0,sq-datasq-top12、ls=NULL13、p-data=x,

31、ls=p14、p-data,free(p)15、*x=ls-data16、更小的“尺度”、遞歸17、隊(duì)、隊(duì)尾、隊(duì)頭18、隊(duì)列初始化InitQueue(Q)、入隊(duì)列EnQueue(Q,X)、出隊(duì)OutQueue(Q,X)、判隊(duì)列空EmptyQueue(Q)、讀隊(duì)頭 ead(Q,x)19、假溢出20、sq-fro nt=021、sq-fro nt,sq-rear=(sq-rear+1)%maxsize,sq-datasq-rear=x22、sq-rear,sq-for nt=(sqrear+1)%maxsize,*x=sq-datasq-rear23、=24、,+1)%maxsize25、隊(duì)滿、隊(duì)

32、空26、lq-fro nt=p,NULL27、p-data,p,lq-rear=p28、*x,s-n ext29、=30、p=n ext,*x31、先進(jìn)后出(后進(jìn)先出)32、先進(jìn)先出(后進(jìn)后出)33、ls= =NULL,*x=p-info34、n-135、棧36、lq-front-next= =lq-rear三、單項(xiàng)選擇題I、2、3、4、5、6、7、8、9、10、II、12、13、14、15、16、17、18、19、20、21、22、23、24、25、四、簡(jiǎn)答及應(yīng)用1、順序棧類型定義如下：#define sqstack maxsize 順序棧的容量typedef struct sqstackD

33、ataType datasqstack maxsizel;int topSqStackTp它有兩個(gè)域： data禾口 top。Data 為一個(gè)一維數(shù)組，用于存儲(chǔ)棧中元素，DataType 為棧元素的數(shù)據(jù)類型。 Top 為int 型，它的實(shí)際取值范圍為0sqstack_maxsize 1。2、鏈棧的類型定義如下：typedef stuct node DataType data;struct node *n ext;LstackTp;單鏈表的第一個(gè)結(jié)點(diǎn)就是鏈棧棧頂結(jié)點(diǎn)，鏈棧由棧頂指針惟一確定。棧中的其它結(jié)點(diǎn)通過(guò)它們的next域鏈接起來(lái)不。棧底結(jié)點(diǎn)的next域?yàn)镹ULL。3、順序隊(duì)列的類型定義如下：

34、#defi ne maxsize 順序棧的容量typedef struct sqqueueDataType datamaxsize;int fornt,rearSqQueueTpSqQueueTp sq;該類型變量有三個(gè)域：data,front,rear。其中data存儲(chǔ)隊(duì)中元素的一維數(shù)組。隊(duì)頭指針front和隊(duì)尾指針rear定義為整型變量，實(shí)際取值范圍為0maxsize 1。循環(huán)隊(duì)列的類型定義如下：#defi ne maxsize循環(huán)隊(duì)的容量typedef struct cycqueueDataType datamaxsizeInt fron t,rearCycqueueTp;Cycqueu

35、eTp sq;_4、typedef struct linked queue DataType data;struct lin ked queue *next;LqueueTp;typedef struct queueptr LqueueTp *front, *rear;QueptrTp;QueptrTp lq;5、#define maxnum非零元素的容量typedef struct node int i,j ;/*非零元素所在的行號(hào)、列號(hào)*/DataType v;/*非零元素的值*/NODE;typedef struct spmatrix_int_mu,nu,tu;/*行數(shù)、列數(shù)、非零元素的

36、個(gè)數(shù)*/_NODE datamaxnum+1;/*這里假定三元組的下標(biāo)的起始值為 1*/SpMatrixTp6、int length(CycqueueTp sq)len= 、 1234、 4321、 2143、 3421、 3241、 1324、 1432、 1342、 1243、 3214、 2134、 2314、 2341、24318、運(yùn)行結(jié)果： ABCDEFGHIJKLMMLKJIHGFEDCBA9、借助棧將一個(gè)帶頭結(jié)點(diǎn)的單鏈表倒置。10f(1)前2r ，3r4r5匚Top-3r4r5匚Top-4r5rTop-5Top-Top-LqueueTp;typedef struct queueptrLqueueTp *fron t,*rear;QueptrTp;int In itStack(SqStackTp *sq) sq-top=0; return(1);void In itQueue (QueptrTp *lp)LqueueTp *p;p=(LqueueTp * )malloc(sizeof(LqueueTp);lq-fro nt=p;lq-rear=p;(lq-fro nt)- next=NULL;in