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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第三章 棧、隊(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.對稱方陣14.上（下）三角矩陣 二、 填空題：1. 棧修改的原則是_或稱_，因此，棧又稱為_線性表。在棧頂進(jìn)行插入運(yùn)算，被稱為_或_，在棧頂進(jìn)行刪除運(yùn)算，被稱為_或_。2. 棧的基本運(yùn)算至少應(yīng)包括_、_、_、_、_五種。3. 對于順序棧，若棧頂下標(biāo)值top=0,此時(shí)，如果作退棧運(yùn)算，則產(chǎn)生“_”。4. 對于順序棧而言，在棧滿狀態(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)在順序棧上的初始化，請?jiān)赺處用適當(dāng)?shù)木渥佑枰蕴畛?。int InitStack(SqStackTp *sq) _;return(1);8. 以下運(yùn)算實(shí)現(xiàn)在順序棧上的進(jìn)棧，請?jiān)赺處用適當(dāng)?shù)恼Z句予以填充。Int Push(SqStackTp *sq,DataType x) if(sp->top=sqstack_maxsize-1error(“棧滿”);return(0); els

3、e_: _=x;return(1); 9. 以下運(yùn)算實(shí)現(xiàn)在順序棧上的退棧，請?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)在順序棧上判?？?，請?jiān)赺處用適當(dāng)句子予以填充。Int EmptyStack(SqStackTp *sq) if(_) return(1); else return(0); 11.以下運(yùn)算實(shí)現(xiàn)在順序棧上取棧頂元素，請?jiān)赺處用適當(dāng)句子予以填充。Int GetTop(SqStackTp *

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

5、taType *x) LstackTp *p; if(ls!=NULL) p=ls; *x=_; ls=ls->next; _; return(1)； else return(0); 15. 以下運(yùn)算實(shí)現(xiàn)在鏈棧上讀棧頂元素，請?jiān)赺處用請適當(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

6、7隊(duì)列簡稱_。在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到_，被刪除的只能是排在_的結(jié)點(diǎn)。18隊(duì)列以線性表為邏輯結(jié)構(gòu)，至少包括_、_、_、_ _、五種基本運(yùn)算。19順序隊(duì)的出、入隊(duì)操作會(huì)產(chǎn)生“_”。20以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的初始化，請?jiān)赺處用適當(dāng)句子予以填充。Void InitCycQueue(CycqueueTp *sq) _;sq->rear=0;21. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的入隊(duì)列，請?jiān)赺處用請適當(dāng)句子予以填充。Int EnCycQueue(CycquereTp *sq,DataType x) if(sq->rear+1)%maxsize= _) error(“隊(duì)滿”);return

7、(0); else _; _ _; return(1); 22. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上的出隊(duì)列，請?jiān)赺處用適當(dāng)句子予以填充。Int OutCycQueue(CycquereTp *sq,DataType *x) if(sq->front= _)error(“隊(duì)空”);return(0)； else _; _; return(1); 23. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上判隊(duì)空，請?jiān)赺處用適當(dāng)句子予以填充。Int EmptyCycQueue(CycqueueTp sq) if(_) return(1); else return(0); 24. 以下運(yùn)算實(shí)現(xiàn)在循環(huán)隊(duì)上取隊(duì)頭，請?jiān)赺處用適當(dāng)句子予以

8、填充。Int GetHead(CycqueueTp sq,DataType *x) if(sq.rear= _return(0); else *x=sq.data_ ; return(1); 25.鏈隊(duì)在一定范圍內(nèi)不會(huì)出現(xiàn)_的情況。當(dāng)lq.front=lq.rear試，隊(duì)中無元素，此時(shí)_。26以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的初始化，請?jiān)赺處用適當(dāng)句子予以填充。void InitQueue(QueptrTp *lp) LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)； _； lq->rear=p; (lq->front)->next=_

9、;27. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的入隊(duì)列，請?jiān)赺處用適當(dāng)句子予以填充。Void EnQueue(QueptrTp *lq,DataType x) LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp); _=x; p->next=NULL; (lq->rear)->next=_; _; 28. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上的出隊(duì)列，請?jiān)赺處用適當(dāng)句子予以填充。int OutQueue(QuetrTp *lq,DataType *x) LqueueTp *s; if(lq->front=lq->rear)erroe(“隊(duì)空”)；r

10、eturn(0); else s=(lq->front)->next; _=s->data; (lq->front)->next=_； if(s->next=NULL) lq->rear=lq->front; free(s); return(1); 29. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上判隊(duì)空，請?jiān)赺處用適當(dāng)句子予以填充int EmptyQueue(QueptrTp *lq) if(_) return(1)； else return(0);30. 以下運(yùn)算實(shí)現(xiàn)在鏈隊(duì)上讀隊(duì)頭元素，請?jiān)赺處用適當(dāng)句子予以填充。Int GetHead(QueptrTp lq,D

11、ataType *x) LqueueTp *p; if(lq.rear=lq.front) return(0); else_; _ =p->data; return(1); 31一般地，一個(gè)n維數(shù)組可視為其數(shù)據(jù)元素為_維數(shù)組的線性表。數(shù)組通常只有_和_兩種基本運(yùn)算。32，通常采用_存儲(chǔ)結(jié)構(gòu)來存放數(shù)組 。對二維數(shù)組可有兩種存儲(chǔ)方法：一種是以_為主序的存儲(chǔ)方式，另一種是以_為主序的存儲(chǔ)方式。C語言數(shù)組用的是以_序?yàn)橹餍虻拇鎯?chǔ)方法；FORTRAN語言用的是以_序?yàn)橹餍虻拇鎯?chǔ)方法33需要壓縮存儲(chǔ)的矩陣可分為_矩陣和_矩陣兩種。34對稱方陣中有近半的元素重復(fù)， 若為每一對元素只分配一個(gè)存儲(chǔ)空間 ，

12、則可將n2個(gè)元素壓縮存儲(chǔ)到_個(gè)元素的存儲(chǔ)空間中。35假設(shè)以一維數(shù)組M（1：n(n+1)/2）作為n階對稱矩陣A的存儲(chǔ)結(jié)構(gòu)，以行序?yàn)橹餍虼鎯?chǔ)其下三角（包括對角線）中的元素，數(shù)組M和矩陣A間對應(yīng)的關(guān)系為_。36上三角矩陣中，主對角線上的第t行(1<=t<=n)有_個(gè)元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時(shí)，aij之前的前i-1行共有_個(gè)元素，在第i行上， aij是該行的第_個(gè)元素，Mk和aij的對應(yīng)關(guān)系是。當(dāng)i>j時(shí)，aij=c,c存放在M_中。37下三角矩陣的存儲(chǔ)和對稱矩陣類似。MK和aij的對應(yīng)關(guān)系是_。38基于三元組的稀疏矩陣轉(zhuǎn)置的處理方法有兩種，以下運(yùn)算按照矩陣A

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

14、處用適當(dāng)?shù)木渥佑靡蕴畛?。Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) (*b).mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu=a.tu; if(a.tu) for(col=1;_;col+) numcol=0; for(t=1;t<=a,tu;t+) numa.datat.j+; cpot1=1; for(col=2;col<=a.nu;col+) cpotcol=_; for(p=1;p<=a.tu;p+) col=a.datap.j; q=cpotcol; (*b).dataq.i=a.datap.j;

15、 (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; 40棧稱為_線性表。 ;41隊(duì)稱為_線性表。42設(shè)一個(gè)鏈棧的棧頂指針為ls，棧中結(jié)點(diǎn)的格式為 info next,?？盏臈l件是_；如果棧不為空，則退棧操作為p=ls; _;ls=ls->next;free(p)。43設(shè)有二為數(shù)組int M1020(注：m為0.10,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)。4

16、6數(shù)組M中每個(gè)元素的長度是3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到0，從首的址EA開始連續(xù)存放在存儲(chǔ)其中。若按行方式存放，元素M85的起始地址為_；若按列優(yōu)先方式存放，元素M85的地址為_。47對帶有頭結(jié)點(diǎn)的列隊(duì)列l(wèi)q,判定隊(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)算的是 （ ）lnitSta

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

18、ar=xsq.datasq.rear=x sq.rear=sq.rear+1sq.rear=(sq.rear+1)% maxsize; sq.datasq.rear=xsq.datasqrear=x sq.rear=(sq.rear+1)% maxsize 5.循環(huán)隊(duì)列的人隊(duì)操作應(yīng)為 ( )sq.rear=sq.rear+1 sq.datasq.rear=xsq.datasq.rear=x sq.rear=sq.rear+1sq.rear=(sq.rear+1)% maxsize sq.datasq.rear=xsq.datasq.rear=x sq.rear=(sq.rear+1)% max

19、size6. 順序隊(duì)列的出隊(duì)操作為 ( ) sq.front=(sq.front+1)% maxsize sq.front=sq.front+1sq.rear=(sq.rear+1)% maxsizesq.rear=sq.rear+17. 循環(huán)隊(duì)列的出隊(duì)操作為 ( )sq.front=(sq.ftont+1)% maxsizesq.front=sq.front+1sq.rear=(sq.rear+)% maxsizesq.rear=sq.rear+18.循環(huán)隊(duì)列的隊(duì)滿條件為 ( )(sq.rear+1) % mazsize =(sq.front+1) % maxsize;(sq.rear+1

20、% maxsize =sq.front+1sq.(rear+1) % maxsize =sq.frontsq.rear =sq.front9.循環(huán)隊(duì)列的隊(duì)空條件為 ( )(sq.rear+1) % maxsize =(sq.front+1) % maxsize(sq.rear+) % maxsize =sq.front+1(sp.rear+1) % maxsize =sq.frontsq.rear = sq.front 10.數(shù)組的數(shù)據(jù)元素類型DataType可根據(jù)實(shí)際需要而定義。以下說法完全正確的是 ( )數(shù)組的讀運(yùn)算可以讀取一個(gè)數(shù)據(jù)元素整體,寫運(yùn)算只能修改一個(gè)數(shù)據(jù)元素的一部分?jǐn)?shù)組的讀、寫運(yùn)

21、算可以讀取或修改一個(gè)數(shù)據(jù)元素的一部分或一個(gè)整體 數(shù)組的讀、寫運(yùn)算只能讀取或修改一個(gè)數(shù)據(jù)元素的一部分?jǐn)?shù)組的讀、寫運(yùn)算只能讀取或修改一個(gè)數(shù)據(jù)元素整體11對于以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)來說，在數(shù)組Ac1···d1，c2···d2中，c1和d1分別為數(shù)組A的第一個(gè)下標(biāo)的上、下界，c2d2分別為第二各下標(biāo)的上、下界，每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任一元素ai,j的存儲(chǔ)位置可由( )式確定.Loci,j=( d2-c2+1)(i- c1)+(j- c2)*kLoci,j=locc1, c2+( d2- c2+1)(i- c1)+(j- c2)

22、*kLoci,j=Ac1, c2+( d2- c2+1)(i- c1)+(j- c2)*kLoci,j=loc0,0+( d2- c2+1)(i- c1)=(j- c2)*k12對于C語言的二維數(shù)組DataType Amn,每個(gè)數(shù)據(jù)元素占K個(gè)存儲(chǔ)單元，二維數(shù)組中任意元素ai,j 的存儲(chǔ)位置可由( )式確定.Loci,j=Am,n+(n+1)*i+j*kLoci,j=loc0,0+(m+n)*i+j*kLoci,j=loc0,0+(n+1)*i+j*kLoci,j=(n+1)*i+j*k13.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種( )的存儲(chǔ)結(jié)構(gòu),線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種（ ）的存儲(chǔ)結(jié)構(gòu)。 隨機(jī)存取 順序

23、存儲(chǔ)14如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作是 ( )必須判別棧是否滿 必須判別棧是否空判別棧元素的類型 對棧不做任何操作15對于基于三元組的稀疏矩陣轉(zhuǎn)置的處埋方法以下說法正確的是 ( )按照矩陣A的列序來進(jìn)行轉(zhuǎn)置，算法的時(shí)間復(fù)雜度為0(nu+tu)按照A的三元組a.data的次序進(jìn)行轉(zhuǎn)置，算法的時(shí)間復(fù)雜度為O(nu*tu)按照矩陣A的列序來進(jìn)行轉(zhuǎn)置的方法稱快速轉(zhuǎn)置按照矩陣A的列序進(jìn)行轉(zhuǎn)置,對于tu<<mu x nu才有意義。16稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ) ( )非零元素 三元祖（i,j, aij） aij i,j17基于三元組的稀疏矩陣，對每個(gè)非零元素aij,可以用一個(gè)（

24、）唯一確定。非零元素 三元組(i,j,aij) aij i,j18如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu),則退棧操作時(shí) ( )必須判別棧是否滿 判別棧元素的類型必須判別棧是否空 隊(duì)棧不做任何判別19設(shè)C語言數(shù)組Datam+1作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間， front為隊(duì)頭指針，rear為隊(duì)為指針，則執(zhí)行出隊(duì)操作的語句為 （ ）front=front+1 front=（front+1）%mrear=(rear+1)%m front=(front+1)%(m+1)20.三角矩陣可壓縮存儲(chǔ)到數(shù)組（ ）中。M1:n(n+1)/2+1 M1:n(n+1)/2Mn(n+1)/2+1 Mn(n+1)/221.設(shè)有一順序棧

25、S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個(gè)元素出線的順序是s2,s3,s4, s6 , s5,s1,則棧的容量至少應(yīng)該是 （ ） 2 3 5 622設(shè)有一順序棧已含3個(gè)元素，如下圖所示，元素a4正等待進(jìn)棧。那么下列4個(gè)序列中不可能出現(xiàn)的出棧序列是 （ ） 0 1 2 3 maxsize-1a1a2a3sq top a3,a1,a4,a2 a3,a2,a4,a1 a3,a4,a2,a1 a4,a3,a2,a123.向一個(gè)棧頂指針為Top的鏈中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟為 （ ）Top->next=s s->next=Top->next;Top->n

26、ext=ss->next=Top;Top=s s->next=Top;Top=Top->next24.從棧頂指針為Top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，并將被刪節(jié)點(diǎn)的值保存到x中，其操作步驟為（ ）x=Top->data;Top=Top->next Top=Top->next;x=Top->datax=Top;Top=Top->next x=Top->data 25.在一個(gè)鏈隊(duì)中，若f,r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（ ）f->next=c;f=s r->next=s;r=ss->next=r;r=s s->

27、next=f;f=s26常對數(shù)組進(jìn)行的兩種基本操作是 （ ）建立與刪除 索引與修改 查找與修改 查找與索引27鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)即 （ ）插入操作更方便 通常不會(huì)出現(xiàn)棧滿的情況不會(huì)出現(xiàn)棧空的情況 刪除操作更方便 28若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn) （ ）正確 錯(cuò)誤29。二為數(shù)組Mi,j的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲(chǔ)單元）組成的串，行下標(biāo)i的范圍從O到4，列下標(biāo)j的范圍從O到5。M按行存儲(chǔ)時(shí)元素M3,5 的起始地址與M按列存儲(chǔ)時(shí)元素( )的起始地址相同。M 2,4 M3,4 M3,5 M4,43

28、0.一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是 （ ） e d c b a d e c b a d c e a b a b c d e31.一個(gè)隊(duì)列的人列序是1，2，3，4，則隊(duì)列的輸出系列是 （ ） 4，3，2，1 1，2，3，4， 1，4，3，2 3，2，4，132設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對出線的算法，采用（ ）數(shù)據(jù)結(jié)構(gòu)最佳。 線性標(biāo)的順序存儲(chǔ)結(jié)構(gòu) 棧 隊(duì)列 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 33若已知一個(gè)棧的輸入序列為1，2，3，.,n,其輸出序列為P1、P2、.Pn。若p1=n,則P1為 i n=i n-i+1 不確定34以下說法正確的是順序隊(duì)和循環(huán)隊(duì)的隊(duì)滿和隊(duì)空判

29、斷條件是一樣的?？梢宰鳛閷?shí)現(xiàn)過程調(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. 以下說法正確的是數(shù)組是同類型值的集合數(shù)組是一組相繼的內(nèi)存單元數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系，既不是線性的，也不是樹形的使用三元組表表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間四、簡答及應(yīng)用1簡述順序棧的類型定義。2簡述鏈棧的類型定義。3簡述順序隊(duì)列、循環(huán)隊(duì)列的類型定義。4簡述鏈隊(duì)的類型定義。5，寫出基于三元組的稀疏矩陣的類型說明。6對

30、于循環(huán)隊(duì)列，試寫出求隊(duì)列長度的算法。7設(shè)有編號(hào)為t，2，3，4的四輛列車。順序進(jìn)入一個(gè)占世界共的展臺(tái)，試寫出這四兩列車開出車站的所有可能的順序。8設(shè)有上三角矩陣(aij)n*n,將其上三角元素逐行存于數(shù)組B(1:m)中（m充分大），使得Bk=aij,且k=f1(i)+f2(j)+c。是推導(dǎo)出函數(shù)f1,f2和常數(shù)c(要求f1和f2中不含常數(shù)項(xiàng))。9設(shè)有三對角矩陣（aij）n*n,將其三條對角線上的元素逐行存于數(shù)組B(1:3n-2)中，使得Bk=aij,求：（1） 用i、j表示k的下標(biāo)變換公式；（2） 用k表示i、j的下標(biāo)變換公式.10.閱讀下列程序，寫出程序的運(yùn)行結(jié)果。# define sqst

31、ack_maxsize 40typedef struct sqstack char datasqstack_maxsize; int top; SqStackTp;main() SqStackTp sq; int i; char ch; 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”);11.閱讀下列算法，寫

32、出其完整的功能。Void reverse_list( LinkedListTP *head) LstackTP ls,p; DataType x; 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)導(dǎo)論課本的圖3-5失利，畫出調(diào)用f(5)是引起的工作棧

33、狀態(tài)變化情況。Int f(int I) if(n=1) return(10); else return(f(I-1)+2);五、算法設(shè)計(jì)1.某汽車輪渡口，過江渡船每次能載10輛車過江。過江車輛分為客車類和貨車類，上渡船的有如下規(guī)定：同類車先到先上船；且每上4輛客車，才允許上一輛貨車；若等待客車不足4輛，則以火車代替，若無貨車等待允許客車都上船。試寫一算法模擬渡口管理?？梢栽谝粋€(gè)數(shù)組中保存兩個(gè)棧：一個(gè)棧以數(shù)組的第一個(gè)單元作為棧底，另一個(gè)棧以數(shù)組的最后一個(gè)單元作為棧底（如下圖所示）。設(shè)S是其中一個(gè)占，是分別編寫過程push(S,X)(元素X入棧)， 出棧pop(S)和取棧頂元素Top(S).題示：

34、設(shè)其中一個(gè)棧為0，另一棧為1。 0 1 2 M-1 M M+1 ······ 棧0底 棧0頂 棧1頂 棧1底3假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的初始化隊(duì)列、入隊(duì)列和出隊(duì)列算法。4假設(shè)以數(shù)組cycquem(假設(shè)數(shù)組范圍在0.m)存放循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素位置和內(nèi)含元素的個(gè)數(shù)。試給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)列和出隊(duì)列的算法。5編寫算法:按行優(yōu)先存儲(chǔ)順序，將稀疏矩陣轉(zhuǎn)換為三元組的表示形式。6稀疏矩陣用三元組的表示

35、形式，試寫一算法實(shí)現(xiàn)兩個(gè)稀疏矩陣相加，結(jié)果仍用三元組表示。7假設(shè)一個(gè)算術(shù)表達(dá)式中可以包含三中括號(hào)：圓括號(hào)“（”和“）”，方括號(hào)“”和“”以及花括號(hào)與“”和“”，且這三種括號(hào)可按任意的次序嵌套試用，如（. . . . . . . .( . . . .)。試?yán)脳５倪\(yùn)算編寫判斷給定表達(dá)式中所含括號(hào)是否正確 配對出現(xiàn)的算法（可設(shè)表達(dá)式已存入字符型數(shù)組中）。8已知Ackerman函數(shù)定義如下：akm(m,n)=試寫出遞歸算法。9設(shè)函數(shù)f(m,n)按下式定義（ m,n為）0的整數(shù)）f(m,n)=試寫出計(jì)算函數(shù)的遞歸過程。10設(shè)有一個(gè)背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為w1,w2,. .，

36、wn.問能否從這n件物品中選擇若干件放入此背包，使得放入的重量之和正好為S.如果存在一種符合上述要求的選擇，則稱此背包問題有解（或承接為真），否則此問題無解（或結(jié)為假），試用遞歸和非遞歸兩種方法設(shè)計(jì)此背包問題的算法。11借助棧(可用棧的基本運(yùn)算)來實(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),判?？誆mpty(S)3、  下溢4、  上溢5、  順序

37、、鏈接6、  ?？铡⑾乱?、棧滿、上溢7、  sq->top=08、  sq->top+,sq->datasq->top9、  sq->datasq->top,sq->top10、              sq->top= =011、            &#

38、160; sq->top= =0,sq->datasq->top12、              ls=NULL13、              p->data=x,ls=p14、           &#

39、160;  p->data,free(p)15、              *x=ls->data16、              更小的“尺度”、遞歸17、              隊(duì)

40、、隊(duì)尾、隊(duì)頭18、              隊(duì)列初始化InitQueue(Q)、入隊(duì)列EnQueue(Q,X)、出隊(duì)OutQueue(Q,X)、判隊(duì)列空EmptyQueue(Q)、讀隊(duì)頭ead(Q,x)19、              假溢出20、       

41、60;      sq->front=021、              sq->front,sq->rear=(sq->rear+1)%maxsize,sq->datasq->rear=x22、              sq->rear,sq-

42、>fornt=(sq->rear+1)%maxsize,*x= sq->datasq->rear23、              sq.rear= sq.front24、              sq.front,(sq.front+1)%maxsize25、    

43、60;         隊(duì)滿、隊(duì)空26、              lq->front=p,NULL27、              p->data,p,lq->rear=p28、     &

44、#160;        *x,s->next29、              lq.rear= =lq.front30、              p=lq.front->next,*x31、先進(jìn)后出（后進(jìn)先出）32、先進(jìn)先出（后進(jìn)后出）33、ls= =N

45、ULL,*x=p->info34、n-135、棧36、lq->front->next= =lq->rear 三、單項(xiàng)選擇題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、  四、簡答及應(yīng)用1、順序棧類型定義如下：#define sqstack_maxsize 順序棧的容量typedef struct sqstackDataType datasqstack_maxsize;int topSqStackTp它有兩個(gè)域：data和top。Data為一個(gè)一維數(shù)組，用

46、于存儲(chǔ)棧中元素，DataType為棧元素的數(shù)據(jù)類型。Top為int型，它的實(shí)際取值范圍為0sqstack_maxsize1。2、鏈棧的類型定義如下：typedef stuct node DataType data; struct node *next;LstackTp;單鏈表的第一個(gè)結(jié)點(diǎn)就是鏈棧棧頂結(jié)點(diǎn)，鏈棧由棧頂指針惟一確定。棧中的其它結(jié)點(diǎn)通過它們的next域鏈接起來不。棧底結(jié)點(diǎn)的next域?yàn)镹ULL。3、順序隊(duì)列的類型定義如下：#define maxsize 順序棧的容量typedef struct sqqueue DataType datamaxsize;int fornt,rearSq

47、QueueTpSqQueueTp sq;該類型變量有三個(gè)域：data,front,rear。其中data存儲(chǔ)隊(duì)中元素的一維數(shù)組。隊(duì)頭指針front和隊(duì)尾指針rear定義為整型變量，實(shí)際取值范圍為0maxsize1。循環(huán)隊(duì)列的類型定義如下：#define maxsize循環(huán)隊(duì)的容量typedef struct cycqueueDataType datamaxsizeInt front,rearCycqueueTp;CycqueueTp sq;4、typedef struct linked_queue DataType data; struct linked_queue *next;LqueueT

48、p;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ù)、非零元素的個(gè)數(shù)*/ NODE datamaxnum+1;/*這里假定三元組的下標(biāo)的起始值為1*/SpMatrixTp6、int length(CycqueueTp sq)len=

49、(sq.rear-sq.front+maxsize)%maxsize;return(len);7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、24318、運(yùn)行結(jié)果：ABCDEFGHIJKLMMLKJIHGFEDCBA9、借助棧將一個(gè)帶頭結(jié)點(diǎn)的單鏈表倒置。10      Top->       Top->      T