1、第三章 棧、隊列和數組一、 名詞解釋：1.棧、棧頂、棧底、棧頂元素、空棧2.順序棧3.鏈棧4.遞歸5.隊列、隊尾、隊頭6.順序隊7.循環隊8.隊滿9.鏈隊10.隨機存儲結構11.特殊矩陣12.稀疏矩陣13.對稱方陣14.上（下）三角矩陣 二、 填空題：1. 棧修改的原則是_或稱_，因此，棧又稱為_線性表。在棧頂進行插入運算，被稱為_或_，在棧頂進行刪除運算，被稱為_或_。2. 棧的基本運算至少應包括_、_、_、_、_五種。3. 對于順序棧，若棧頂下標值top=0,此時，如果作退棧運算，則產生“_”。4. 對于順序棧而言，在棧滿狀態下，如果此時在作進棧運算，則會發生“_”。5. 一般地，棧和線性

2、表類似有兩種實現方法，即_實現和_實現。6. top=0表示_，此時作退棧運算，則產生“_”；top=sqstack_maxsize-1表示_，此時作進棧運算，則產生“_”。7. 以下運算實現在順序棧上的初始化，請在_處用適當的句子予以填充。int InitStack(SqStackTp *sq) _;return(1);8. 以下運算實現在順序棧上的進棧，請在_處用適當的語句予以填充。Int Push(SqStackTp *sq,DataType x) if(sp-top=sqstack_maxsize-1error(“棧滿”);return(0); else_: _=x;return(1)

3、; 9. 以下運算實現在順序棧上的退棧，請在_用適當句子予以填充。Int Pop(SqStackTp *sq,DataType *x) if(sp-top=0)error(“下溢”);return(0); else*x=_; _; return(1); 10. 以下運算實現在順序棧上判棧空，請在_處用適當句子予以填充。Int EmptyStack(SqStackTp *sq) if(_) return(1); else return(0); 11.以下運算實現在順序棧上取棧頂元素，請在_處用適當句子予以填充。Int GetTop(SqStackTp *sq,DataType *x) if(_)

4、 return(0); else*x=_; return(1); 12. 以下運算實現在鏈棧上的初始化，請在_處用請適當句子予以填充。Void InitStacl(LstackTp *ls) _;13. 以下運算實現在鏈棧上的進棧，請在處用請適當句子予以填充。Void Push（LStackTp *ls,DataType x） LstackTp *p;p=malloc(sizeof(LstackTp); _; p-next=ls; _; 14以下運算實現在鏈棧上的退棧，請在_處用請適當句子予以填充。Int Pop(LstackTp *ls,DataType *x) LstackTp *p; i

5、f(ls!=NULL) p=ls; *x=_; ls=ls-next; _; return(1)； else return(0); 15. 以下運算實現在鏈棧上讀棧頂元素，請在_處用請適當句子予以填充。Int Get Top(LstackTp *ls,DataType *x) if(ls!=NULL) _;return(1); else return(0); 16.必須注意，遞歸定義不能是“循環定義”。為此要求任何遞歸定義必須同時滿足如下條件：被定義項在定義中的應用（即作為定義項的出現）具有_；被定義項在最小“尺度”上的定義不是_的。17隊列簡稱_。在隊列中，新插入的結點只能添加到_，被刪除的

6、只能是排在_的結點。18隊列以線性表為邏輯結構，至少包括_、_、_、_ _、五種基本運算。19順序隊的出、入隊操作會產生“_”。20以下運算實現在循環隊上的初始化，請在_處用適當句子予以填充。Void InitCycQueue(CycqueueTp *sq) _;sq-rear=0;21. 以下運算實現在循環隊上的入隊列，請在_處用請適當句子予以填充。Int EnCycQueue(CycquereTp *sq,DataType x) if(sq-rear+1)%maxsize= _) error(“隊滿”);return(0); else _; _ _; return(1); 22. 以下運算

7、實現在循環隊上的出隊列，請在_處用適當句子予以填充。Int OutCycQueue(CycquereTp *sq,DataType *x) if(sq-front= _)error(“隊空”);return(0)； else _; _; return(1); 23. 以下運算實現在循環隊上判隊空，請在_處用適當句子予以填充。Int EmptyCycQueue(CycqueueTp sq) if(_) return(1); else return(0); 24. 以下運算實現在循環隊上取隊頭，請在_處用適當句子予以填充。Int GetHead(CycqueueTp sq,DataType *x)

8、 if(sq.rear= _return(0); else *x=sq.data_ ; return(1); 25.鏈隊在一定范圍內不會出現_的情況。當lq.front=lq.rear試，隊中無元素，此時_。26以下運算實現在鏈隊上的初始化，請在_處用適當句子予以填充。void InitQueue(QueptrTp *lp) LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)； _； lq-rear=p; (lq-front)-next=_;27. 以下運算實現在鏈隊上的入隊列，請在_處用適當句子予以填充。Void EnQueue(Queptr

9、Tp *lq,DataType x) LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp); _=x; p-next=NULL; (lq-rear)-next=_; _; 28. 以下運算實現在鏈隊上的出隊列，請在_處用適當句子予以填充。int OutQueue(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=

10、NULL) lq-rear=lq-front; free(s); return(1); 29. 以下運算實現在鏈隊上判隊空，請在_處用適當句子予以填充int EmptyQueue(QueptrTp *lq) if(_) return(1)； else return(0);30. 以下運算實現在鏈隊上讀隊頭元素，請在_處用適當句子予以填充。Int GetHead(QueptrTp lq,DataType *x) LqueueTp *p; if(lq.rear=lq.front) return(0); else_; _ =p-data; return(1); 31一般地，一個n維數組可視為其數據元

11、素為_維數組的線性表。數組通常只有_和_兩種基本運算。32，通常采用_存儲結構來存放數組 。對二維數組可有兩種存儲方法：一種是以_為主序的存儲方式，另一種是以_為主序的存儲方式。C語言數組用的是以_序為主序的存儲方法；FORTRAN語言用的是以_序為主序的存儲方法33需要壓縮存儲的矩陣可分為_矩陣和_矩陣兩種。34對稱方陣中有近半的元素重復， 若為每一對元素只分配一個存儲空間 ，則可將n2個元素壓縮存儲到_個元素的存儲空間中。35假設以一維數組M（1：n(n+1)/2）作為n階對稱矩陣A的存儲結構，以行序為主序存儲其下三角（包括對角線）中的元素，數組M和矩陣A間對應的關系為_。36上三角矩陣中

12、，主對角線上的第t行(1=tj時，aij=c,c存放在M_中。37下三角矩陣的存儲和對稱矩陣類似。MK和aij的對應關系是_。38基于三元組的稀疏矩陣轉置的處理方法有兩種，以下運算按照矩陣A的列序來進行轉置，請在_處用適當的句子用以填充。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=

13、a.datap.i; (*b).dataq.v=a.datap.v; _; 39基于三元組的稀疏矩陣轉置的處理方法有兩種，以下計算按照矩陣A的三元組a.data的次序進行轉置，請在_處用適當的句子用以填充。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+)

14、cpotcol=_; for(p=1;pnext;free(p)。43設有二為數組int M1020(注：m為0.10,n為0.20),每個元素（整數）棧兩個存儲單元，數組的起始地址為2000，元素M510的存儲位置為_，M819的存儲值為_。44在具有n個單元的循環隊列中，隊滿時共有_個元素。45_可以作為實現遞歸函數調用的一種數據結構。46數組M中每個元素的長度是3個字節，行下標i從1到8，列下標j從1到0，從首的址EA開始連續存放在存儲其中。若按行方式存放，元素M85的起始地址為_；若按列優先方式存放，元素M85的地址為_。47對帶有頭結點的列隊列lq,判定隊列中只有一個數據元素的條件是

15、_。48二維數組M的成員是6個字符（每個字符棧一個存儲單元）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要_個字節；M的第8列和第5行共占_個字節；若M按行方式存儲，元素M85的起始地址與當M按列優先方式存儲時的_元素的起始地址一致。 三、單項選擇題1在以下棧的基本運算中，不是加工型運算的是 （ ）lnitStack(S) Push(S,X) Pop(S) empty(S)2.以下說法正確的是 ( )因鏈棧本身沒有容量限制,故在用戶內存空間的范圍內不會出現棧滿情況因順序棧本身沒有容量限制,故在用戶內存空間的范圍內不會出現棧滿情況對于鏈棧而言,在棧滿狀態下,如果此時

16、再作進棧運算，則會發生“上溢”對于順序棧而言在棧滿狀態下如果此時再作迸棧運算，則會發生“下溢”。3在以下隊列的基本運算中，不是加工型運算的是 （ ）InitQueue(Q) EnQueue(Q,X) OutQueu(Q,X) GetHead(Q,x)4.順序隊列的人隊操作應為 ( )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.datasqrear=x sq.rear=(sq.rear+1)% maxsize

17、 5.循環隊列的人隊操作應為 ( )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)% maxsize6. 順序隊列的出隊操作為 ( ) sq.front=(sq.front+1)% maxsize sq.front=sq.front+1sq.rear=(sq.rear+1)% maxsizesq.rear=sq.rear+17. 循環隊列的出隊操

18、作為 ( )sq.front=(sq.ftont+1)% maxsizesq.front=sq.front+1sq.rear=(sq.rear+)% maxsizesq.rear=sq.rear+18.循環隊列的隊滿條件為 ( )(sq.rear+1) % mazsize =(sq.front+1) % maxsize;(sq.rear+1 % maxsize =sq.front+1sq.(rear+1) % maxsize =sq.frontsq.rear =sq.front9.循環隊列的隊空條件為 ( )(sq.rear+1) % maxsize =(sq.front+1) % maxsi

19、ze(sq.rear+) % maxsize =sq.front+1(sp.rear+1) % maxsize =sq.frontsq.rear = sq.front 10.數組的數據元素類型DataType可根據實際需要而定義。以下說法完全正確的是 ( )數組的讀運算可以讀取一個數據元素整體,寫運算只能修改一個數據元素的一部分數組的讀、寫運算可以讀取或修改一個數據元素的一部分或一個整體 數組的讀、寫運算只能讀取或修改一個數據元素的一部分數組的讀、寫運算只能讀取或修改一個數據元素整體11對于以行序為主序的存儲結構來說，在數組Ac1d1，c2d2中，c1和d1分別為數組A的第一個下標的上、下界，

20、c2d2分別為第二各下標的上、下界，每個數據元素占K個存儲單元，二維數組中任一元素ai,j的存儲位置可由( )式確定.Loci,j=( d2-c2+1)(i- c1)+(j- c2)*kLoci,j=locc1, c2+( d2- c2+1)(i- c1)+(j- c2)*kLoci,j=Ac1, c2+( d2- c2+1)(i- c1)+(j- c2)*kLoci,j=loc0,0+( d2- c2+1)(i- c1)=(j- c2)*k12對于C語言的二維數組DataType Amn,每個數據元素占K個存儲單元，二維數組中任意元素ai,j 的存儲位置可由( )式確定.Loci,j=Am,

21、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.線性表的順序存儲結構是一種( )的存儲結構,線性表的鏈式存儲結構是一種（ ）的存儲結構。 隨機存取 順序存儲14如果以鏈表作為棧的存儲結構，則退棧操作是 ( )必須判別棧是否滿 必須判別棧是否空判別棧元素的類型 對棧不做任何操作15對于基于三元組的稀疏矩陣轉置的處埋方法以下說法正確的是 ( )按照矩陣A的列序來進行轉置，算法的時間復雜度為0(nu+tu)按照A的三元組a.data的次序進行轉置，算法的時間復雜度為O(nu*tu)

22、按照矩陣A的列序來進行轉置的方法稱快速轉置按照矩陣A的列序進行轉置,對于tunext=s s-next=Top-next;Top-next=ss-next=Top;Top=s s-next=Top;Top=Top-next24.從棧頂指針為Top的鏈棧中刪除一個結點，并將被刪節點的值保存到x中，其操作步驟為（ ）x=Top-data;Top=Top-next Top=Top-next;x=Top-datax=Top;Top=Top-next x=Top-data 25.在一個鏈隊中，若f,r分別為隊首、隊尾指針，則插入s所指結點的操作為（ ）f-next=c;f=s r-next=s;r=ss

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

24、3,4 M3,5 M4,430.一個棧的入棧序列是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.一個隊列的人列序是1，2，3，4，則隊列的輸出系列是 （ ） 4，3，2，1 1，2，3，4， 1，4，3，2 3，2，4，132設計一個判別表達式中左、右括號是否配對出線的算法，采用（ ）數據結構最佳。 線性標的順序存儲結構 棧 隊列 線性表的鏈式存儲結構 33若已知一個棧的輸入序列為1，2，3，.,n,其輸出序列為P1、P2、.Pn。若p1=n,則P1為 i n=i n-i+1 不確定34以下說法正確的是

25、順序隊和循環隊的隊滿和隊空判斷條件是一樣的棧可以作為實現過程調用的一種數據結構插人和刪除操作是數據結構中最基本的兩種操作，所以這兩種操作在數組中也經常使用在循環隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件front=rear35. 以下說法正確的是數組是同類型值的集合數組是一組相繼的內存單元數組是一種復雜的數據結構，數組元素之間的關系，既不是線性的，也不是樹形的使用三元組表表示稀疏矩陣的元素，有時并不能節省存儲空間四、簡答及應用1簡述順序棧的類型定義。2簡述鏈棧的類型定義。3簡述順序隊列、循環隊列的類型定義。4簡述鏈隊的類型定義。5，寫出基于三元

26、組的稀疏矩陣的類型說明。6對于循環隊列，試寫出求隊列長度的算法。7設有編號為t，2，3，4的四輛列車。順序進入一個占世界共的展臺，試寫出這四兩列車開出車站的所有可能的順序。8設有上三角矩陣(aij)n*n,將其上三角元素逐行存于數組B(1:m)中（m充分大），使得Bk=aij,且k=f1(i)+f2(j)+c。是推導出函數f1,f2和常數c(要求f1和f2中不含常數項)。9設有三對角矩陣（aij）n*n,將其三條對角線上的元素逐行存于數組B(1:3n-2)中，使得Bk=aij,求：（1） 用i、j表示k的下標變換公式；（2） 用k表示i、j的下標變換公式.10.閱讀下列程序，寫出程序的運行結果

27、。# define sqstack_maxsize 40typedef struct sqstack char datasqstack_maxsize; int top; SqStackTp;main() SqStackTp sq; int i; char ch; InitStack(&sq); For(ch=A;chnext; While(p!=NULL) Push(&lsdata); p=p-next; p=head-next; While(! EmptyStack(&ls) Pop(&l,&x); p-data=x; p=p-next; 12，對下列函數，按照數據結構導論課本的圖3-5失

28、利，畫出調用f(5)是引起的工作棧狀態變化情況。Int f(int I) if(n=1) return(10); else return(f(I-1)+2);五、算法設計1.某汽車輪渡口，過江渡船每次能載10輛車過江。過江車輛分為客車類和貨車類，上渡船的有如下規定：同類車先到先上船；且每上4輛客車，才允許上一輛貨車；若等待客車不足4輛，則以火車代替，若無貨車等待允許客車都上船。試寫一算法模擬渡口管理。可以在一個數組中保存兩個棧：一個棧以數組的第一個單元作為棧底，另一個棧以數組的最后一個單元作為棧底（如下圖所示）。設S是其中一個占，是分別編寫過程push(S,X)(元素X入棧)， 出棧pop(S

29、)和取棧頂元素Top(S).題示：設其中一個棧為0，另一棧為1。 0 1 2 M-1 M M+1 棧0底 棧0頂 棧1頂 棧1底3假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素結點（注意不設頭指針），試編寫相應的初始化隊列、入隊列和出隊列算法。4假設以數組cycquem(假設數組范圍在0.m)存放循環隊列的元素，同時設變量rear和quelen分別指示循環隊列中隊尾元素位置和內含元素的個數。試給出此循環隊列的隊滿條件，并寫出相應的入隊列和出隊列的算法。5編寫算法:按行優先存儲順序，將稀疏矩陣轉換為三元組的表示形式。6稀疏矩陣用三元組的表示形式，試寫一算法實現兩個稀疏矩陣相加，結

30、果仍用三元組表示。7假設一個算術表達式中可以包含三中括號：圓括號“（”和“）”，方括號“”和“”以及花括號與“”和“”，且這三種括號可按任意的次序嵌套試用，如（. . . . . . . .( . . . .)。試利用棧的運算編寫判斷給定表達式中所含括號是否正確 配對出現的算法（可設表達式已存入字符型數組中）。8已知Ackerman函數定義如下：akm(m,n)=試寫出遞歸算法。9設函數f(m,n)按下式定義（ m,n為）0的整數）f(m,n)=試寫出計算函數的遞歸過程。10設有一個背包可以放入的物品重量為S，現有n件物品，重量分別為w1,w2,. .，wn.問能否從這n件物品中選擇若干件放入

31、此背包，使得放入的重量之和正好為S.如果存在一種符合上述要求的選擇，則稱此背包問題有解（或承接為真），否則此問題無解（或結為假），試用遞歸和非遞歸兩種方法設計此背包問題的算法。11借助棧(可用棧的基本運算)來實現單鏈表的逆置運算。第 3 章 棧和隊列 參考答案一、名詞解釋（略）二、填空題1、 先進后出、后進先出，后進先出，進棧，入棧，退棧，出棧2、 初始化InitStack(S)、進棧Push(S,X), 退棧Pop(S)，讀棧頂Top(S),判棧空Empty(S)3、 下溢4、 上溢5、 順序、鏈接6、 棧空、下溢、棧滿、上溢7、 sq-top=08、 sq-top+,sq-datasq-t

32、op9、 sq-datasq-top,sq-top10、 sq-top= =011、 sq-top= =0,sq-datasq-top12、 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-

33、datasq-rear=x22、 sq-rear,sq-fornt=(sq-rear+1)%maxsize,*x= sq-datasq-rear23、 sq.rear= sq.front24、 sq.front,(sq.front+1)%maxsize25、 隊滿、隊空26、 lq-front=p,NULL27、 p-data,p,lq-rear=p28、 *x,s-next29、 lq.rear= =lq.front30、 p=lq.front-next,*x31、先進后出（后進先出）32、先進先出（后進后出）33、ls= =NULL,*x=p-info34、n-135、棧36、lq-fro

34、nt-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、順序棧類型定義如下：#define sqstack_maxsize 順序棧的容量typedef struct sqstackDataType datasqstack_maxsize;int topSqStackTp它有兩個域：data和top。Data為一個一維數組，用于存儲棧中元素，DataType為棧元素的數據類型。Top為int型，它的實際取值范圍為0sqstack_maxsize

35、1。2、鏈棧的類型定義如下：typedef stuct node DataType data; struct node *next;LstackTp;單鏈表的第一個結點就是鏈棧棧頂結點，鏈棧由棧頂指針惟一確定。棧中的其它結點通過它們的next域鏈接起來不。棧底結點的next域為NULL。3、順序隊列的類型定義如下：#define maxsize 順序棧的容量typedef struct sqqueue DataType datamaxsize;int fornt,rearSqQueueTpSqQueueTp sq;該類型變量有三個域：data,front,rear。其中data存儲隊中元素的一

36、維數組。隊頭指針front和隊尾指針rear定義為整型變量，實際取值范圍為0maxsize1。循環隊列的類型定義如下：#define maxsize循環隊的容量typedef struct cycqueueDataType datamaxsizeInt front,rearCycqueueTp;CycqueueTp sq;4、typedef struct linked_queue DataType data; struct linked_queue *next;LqueueTp;typedef struct queueptr LqueueTp *front, *rear;QueptrTp;QueptrTp lq;5、#def