數據結構課程課后習題答案(編輯修改稿)

　

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