【文章內(nèi)容簡介】 為MaxSize，則判定st棧為棧空的條件為（ ）。==1 !=1!=MaxSize ==MaxSize答：A（6）設(shè)順序棧st的棧頂指針top的初始時為1，?？臻g大小為MaxSize，則判定st棧為棧滿的條件是 。!=1 ==1!=MaxSize1 ==MaxSize1答：D（7）隊列中元素的進出原則是（ ）。 答：A（8）元素A、B、C、D順序連續(xù)進入隊列qu后，隊頭元素是（ ① ），隊尾元素是（ ② ）。 答：①A ②D。（9）一個隊列的入列序列為1234，則隊列可能的輸出序列是（ ）。 答：B（10）循環(huán)隊列qu（隊頭指針front指向隊首元素的前一位置，隊尾指針rear指向隊尾元素的位置）的隊滿條件是（ ）。A. (+1)%MaxSize==(+1)%MaxSizeB. (+1)%MaxSize==+1C.(+1)%MaxSize====答：C（11）循環(huán)隊列qu（隊頭指針front指向隊首元素的前一位置，隊尾指針rear指向隊尾元素的位置）的隊空條件是（ ）。A. (+1)%MaxSize==(+1)%MaxSizeB. (+1)%MaxSize==+1C.(+1)%MaxSize====答：D（12）設(shè)循環(huán)隊列中數(shù)組的下標是0～N1，其頭尾指針分別為f和r（隊頭指針f指向隊首元素的前一位置，隊尾指針r指向隊尾元素的位置），則其元素個數(shù)為（ ）。 C.(rf)％N+1 D.(rf+N)％N答：D（13）設(shè)有4個數(shù)據(jù)元素a、b、c和d，對其分別進行棧操作或隊操作。在進?；蜻M隊操作時，按a、b、c、d次序每次進入一個元素。假設(shè)?；蜿牭某跏紶顟B(tài)都是空?，F(xiàn)要進行的棧操作是進棧兩次，出棧一次，再進棧兩次，出棧一次；這時，第一次出棧得到的元素是（ ① ），第二次出棧得到的元素是（ ② ）；類似地，考慮對這4個數(shù)據(jù)元素進行的隊操作是進隊兩次，出隊一次，再進隊兩次，出隊一次；這時，第一次出隊得到的元素是（ ③ ），第二次出隊得到的元素是（ ④ ）。經(jīng)操作后，最后在棧中或隊中的元素還有（ ⑤ ）個。①～④： ⑤： 答：①B ②D ③A ④B ⑤B（14）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1～e6依次通過棧S，一個元素出后即進隊列Q，若6個元素出隊的序列是eeeeee1，則棧S的容量至少應(yīng)該是（ ）。 答：C2. 填空題（1）棧是一種特殊的線性表，允許插入和刪除運算的一端稱為（ ① ）。不允許插入和刪除運算的一端稱為（ ② ）。答：①棧頂 ②棧底（2）一個棧的輸入序列是12345，的輸出序列為12345，其進棧出棧的操作為（ ）。答：1進棧，1出棧，2進棧，2出棧，3進棧，3出棧，4進棧，4出棧，5進棧，5出棧。（3）有5個元素，其進棧次序為A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出棧（即C第一個且D第二個出棧）的次序有（ ）。答：CDBAE、CDEBA、CDBEA。（4）順序棧用data[0..n1]存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，則元素x進棧的操作是（ ）。答：data[top]=x。 top++。（5）順序棧用data[0..n1]存儲數(shù)據(jù)，棧頂指針為top，其初始值為0，則出棧元素x的操作是（ ）。答：top。 x=data[top]。（6）（ ）是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。答：隊列（7）設(shè)有數(shù)組A[0..m]作為循環(huán)隊列的存儲空間，front為隊頭指針（它指向隊首元素的前一位置），rear為隊尾指針（它指向隊尾元素的位置），則元素x執(zhí)行入隊的操作是（ ）。答：rear=(rear+1)%(m+1)。 A[rear]=x。（8）設(shè)有數(shù)組A[0..m]作為循環(huán)隊列的存儲空間，front為隊頭指針（它指向隊首元素的前一位置），rear為隊尾指針（它指向隊尾元素的位置），則元素出隊并保存到x中的操作是（ ）。答：front=(front+1)%(m+1)。 x=A[rear]。3. 簡答題（1）簡要說明線性表、棧與隊的異同點。答：相同點：都屬地線性結(jié)構(gòu)，都可以用順序存儲或鏈表存儲；棧和隊列是兩種特殊的線性表，即受限的線性表，只是對插入、刪除運算加以限制。不同點：①運算規(guī)則不同，線性表為隨機存取，而棧是只允許在一端進行插入、刪除運算，因而是后進先出表LIFO；隊列是只允許在一端進行插入、另一端進行刪除運算，因而是先進先出表FIFO。②用途不同，棧用于子程調(diào)用和保護現(xiàn)場等，隊列用于多道作業(yè)處理、指令寄存及其他運算等等。（2）順序隊的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊列是空還是滿？答：一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的上界，不能再有進隊操作，但其實數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊列是解決假溢出的途徑。另外，解決循環(huán)隊列是空還是滿的辦法如下：① 設(shè)置一個布爾變量以區(qū)別隊滿還是隊空；② 浪費一個元素的空間，用于區(qū)別隊滿還是隊空。③ 使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）。通常采用法②，讓隊頭指針front指向隊首元素的前一位置，隊尾指針rear指向隊尾元素的位置，這樣判斷循環(huán)隊列隊空標志是：front=rear，隊滿標志是：(rear+1)%MaxSize=front。4. 算法設(shè)計題（1）假設(shè)采用順序棧存儲結(jié)構(gòu)，設(shè)計一個算法，利用棧的基本運算返回指定棧中棧底元素，要求仍保持棧中元素不變。這里只能使用棧st的基本運算來完成，[0]來得到棧底元素。解：假定采用順序棧結(jié)構(gòu)。先退棧st中所有元素，利用一個臨時棧tmpst存放從st棧中退棧的元素，最后的一個元素即為所求，然后將臨時棧tmpst中的元素逐一出棧并進棧到st中，這樣恢復(fù)st棧中原來的元素。對應(yīng)算法如下：int GetBottom(SqStack st,ElemType amp。x){ ElemType e。 SqStack tmpst。 //定義臨時棧 InitStack(tmpst)。 //初始化臨時棧 if (StackEmpty(st)) //空棧返回0 return 0。 while (!StackEmpty(st)) //臨時棧tmpst中包含st棧中逆轉(zhuǎn)元素 { Pop(st,x)。 Push(tmpst,x)。 } while (!StackEmpty(tmpst)) //恢復(fù)st棧中原來的內(nèi)容 { Pop(tmpst,e)。 Push(st,e)。 } return 1。 //返回1表示成功}（2）設(shè)計一個算法，采用一個順序棧逆向輸出單鏈表L中所有元素。解：本題并不需要改變單鏈表L的結(jié)構(gòu)。設(shè)置一個順序棧st，先遍歷單鏈表并將所有元素進棧，然后棧不空循環(huán)并輸出棧中所有元素。對應(yīng)算法如下：void ReverseDisp(SLink *L){ ElemType x。 struct node { ElemType data[MaxSize]。 int top。 } st。 //定義一個順序棧 =1。 SLink *p=Lnext。 while (p!=NULL) //遍歷單鏈表，將所有元素進棧 { ++。 []=pdata。 p=pnext。 } while (!=1) //棧不空循環(huán)，輸出棧中所有元素 { x=[]。 。 printf(%d ,x)。 } printf(\n)。}（3）設(shè)計一個循環(huán)隊列，用front和rear分別作為隊頭和隊尾指針，另外用一個標志tag標識隊列可能空（0）或可能滿（1），這樣加上front==rear可以作為隊空或隊滿的條件。要求設(shè)計隊列的相關(guān)基本運算算法。解：設(shè)計的隊列的類型如下：typedef struct { ElemType data[MaxSize]。 int front,rear。 //隊頭和隊尾指針 int tag。 //為0表示隊空,為1時表示不空} QueueType。初始時tag=0，進行成功的插入操作后tag=1，進行成功的刪除操作后tag=0；因為只有在插入操作后隊列才有可能滿，只有在刪除操作后隊列才有可能空，因此，這樣的隊列的基本要素如下：初始時：tag=0，front=rear隊空條件：== amp。amp。 ==0隊滿條件：== amp。amp。 ==1對應(yīng)的算法如下：//初始化隊列算法void InitQueue1(QueueType amp。qu){ ==0。 =0。 //為0表示隊空可能為空}//判隊空算法int QueueEmpty1(QueueType qu){ return(== amp。amp。 ==0)。}//判隊滿算法int QueueFull1(QueueType qu) { return(==1 amp。amp。 ==)。}//進隊算法int enQueue1(QueueType amp。qu,ElemType x){ if (QueueFull1(qu)==1) //隊滿 return 0。 =(+1)%MaxSize。 []=x。 =1。 //至少有一個元素,可能滿 return 1。}//出隊算法int deQueue1(QueueType amp。qu,ElemType amp。x)//出隊{ if (QueueEmpty1(qu)==1) //隊空 return 0。 =(+1)%MaxSize。 x=[]。 =0。 //出隊一個元素,可能空 return 1。}（4）假設(shè)用一個循環(huán)單鏈表表示隊列，并且只設(shè)一個指針rear指向隊尾結(jié)點，但不設(shè)頭指針，設(shè)計出相應(yīng)的隊初始化、進隊、出隊和判隊空的算法。解：假設(shè)鏈隊是不帶頭結(jié)點的循環(huán)單鏈表。隊空條件：rear==NULL；進隊操作：在*rear結(jié)點之后插入結(jié)點并讓rear指向該結(jié)點；出隊操作：刪除*rear結(jié)點之后的一個結(jié)點。對應(yīng)的算法如下： 不帶頭結(jié)點的循環(huán)單鏈表表示隊列typedef struct node{ ElemType data。 struct node *next。} QNode。 //鏈隊結(jié)點類型//初始化隊列void InitQueue(QNode *amp。rear){ rear=NULL。}//進隊算法void EnQueue(QNode *amp。rear,ElemType x){ QNode *s。 s=(QNode *)malloc(sizeof(QNode))。 //創(chuàng)建新結(jié)點 sdata=x。 if (rear==NULL) //原鏈隊為空 { snext=s。 //構(gòu)成循環(huán)鏈表 rear=s。 } else { snext=rearnext。 //將*s結(jié)點插入到*rear結(jié)點之后 rearnext=s。 rear=s。 //讓rear指向這個新插入的結(jié)點 }}//出隊算法int DeQueue(QNode *amp。rear,ElemType amp。x){ QNode *q。 if (rear==NULL) //隊空 return 0。 else if (rearnext==rear) //原隊中只有一個結(jié)點 { x=reardata。 free(rear)。 rear=NULL。 } else //原隊中有兩個或以上的結(jié)點 { q=rearnext。 x=qdata。 rearnext=qnext。 free(q)。 } return 1。}//判隊空算法int QueueEmpty(QNode *rear){ return(rear==NULL)。}上機實驗題3假設(shè)以I和O字符分別表示進棧和出棧操作，棧的初態(tài)和終棧均為空，進棧和出棧的操作序列可表示為僅由I和O組成的序列。如IOIIOIOO序列是合法的，而IOOIOIIO序列是不合法的。設(shè)計一個算法判定所給的操作序列是否合法。若合法返回1；否則返回0。（假設(shè)被判定的操作序列已存入一維數(shù)組中）。并用相關(guān)數(shù)據(jù)進行測試。解：采用一個鏈棧來判斷操作序列是否合法，其中str為存放操作序列的字符數(shù)組，n為該數(shù)組的元素個數(shù)（這里的ElemType類型設(shè)定為char）。對應(yīng)的算法如下：include include typedef struct node{ char data。 struct node *next。} LStack。 //鏈棧結(jié)點類型void InitStack(LStack *amp。ls) //初始化棧運算算法{ ls=NULL。}void DestroyStack(LStack *amp。ls) //銷毀棧運算算法{ LStack *pre=ls,*p。 if (pre==NULL) return。 //考慮空棧的情況