1、習題三參考答案備注：紅色字體標明的是與書本內容有改動的內容、選擇題1 .在棧中存取數據的原則是（B ）。A.先進先出B.先進后出C.后進后出D.沒有限制2 .若將整數1、2、3、4依次進棧，則不可能得到的出棧序列是（ D ）。A. 1234 B. 1324 C. 4321 D. 14233 .在鏈棧中，進行出棧操作時（ B ）。A.需要判斷棧是否滿B.需要判斷棧是否為空C.需要判斷棧元素的類型D.無需對棧作任何差別4.在順序棧中，若棧頂指針判空條件是（A ）。top指向棧頂元素的下一個存儲單元，且順序棧的最大容量是maxSize,貝U順序棧的A . top=0 B.top=-1C. top=m

2、axSize D.top=maxSize-15.在順序棧中，若棧頂指針判滿的條件是（C ）。top指向棧頂元素的下一個存儲單元，且順序棧的最大容量是maxSize。則順序棧的A . top=0 B.top=-1 C. top=maxSize D.top=maxSize-16 .在隊列中存取數據元素的原則是（ A ）。A.先進先出B.先進后出C.后進后出D.沒有限制front和rear分別為隊首maxSize,則隊7 .在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件,和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為列的判空條件是（A ）。

3、A. front=rearB. front!=rearC. front=rear+1D. front=（rear+1）% maxSize8.在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize,則隊列的判滿條件是（D ）。A. front=rearB. front!=rearC. front=rear+1D. front=（rear+1）% maxSize9.在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rea

4、r分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize,則隊列的長度是（C ）。A. rear-frontB. rear-front+1C. （rear-front+maxSize）%maxSize D. （rear-front+1）%maxSize10.設長度為n的鏈隊列采用單循環鏈表加以表示，若只設一個頭指針指向隊首元素，則入隊操作的時間復雜度 為（B ）。A. O（1） B. O（n） C. O（log2n）D. O（n2）、填空題1 .棧是一種操作受限的特殊線性表，其特殊性體現在其插入和刪除操作都限制在表尾 進行。允許插入和刪除操作的

5、一端稱為棧頂，而另一端稱為棧底。棧具有后進先出的特點。2 .棧也有兩種存儲結構，一種是順序存儲,另一種是鏈式存儲；以這兩種存儲結構存儲的棧分別稱為順序棧和鏈棧 。3 .在順序棧中，假設棧頂指針top是指向棧頂元素的下一個存儲單元，則順序棧判空的條件是top=0 ;棧頂元素的訪問形式是 stackElemtop-1 ;4 .在不帶表頭結點的鏈棧中，若棧頂指針top直接指向棧頂元素，則將一個新結點p入棧時修改鏈的兩個對應語句為 p.setNext(top) ; top=p; 。5 .在不帶表頭結點的鏈棧中，若棧頂指針top直接指向棧頂元素，則棧頂元素出棧時的修改鏈的對應語句為top=top.get

6、Next(); 。6 .隊列也是一種操作受限的線性表，它與棧不同的是，隊列中所有的插入操作均限制在表的一端進行，而所有 的刪除操作都限制在表的另一端進行，允許插入的一端稱為隊尾，允許刪除的一端稱為隊首。隊列具有先進先出的特點。7 .由于隊列的刪除和插入操作分別在隊首和隊尾進行，因此，在鏈式存儲結構描述中分別需要設置兩個指針分別指向隊首結點和隊尾結點，這兩個指針又分別稱為 隊首指針和隊尾指針。8 .循環順序隊列是將順序隊列的存儲區域看成是一個首尾相連的環，首尾相連的狀態是通過數學上的求模(或取余)運算來實現的。9 .在循環順序隊列中，若規定當 front=rear 時，循環隊列為空；當 fron

7、t=(rear+1)%maxSize 時，循環隊列 為滿，則入隊操作時的隊尾指針變化的相應語句是 rear=(rear+1)% maxSize ;出隊操作時的隊首指針變化 的相應語句是 front=(front+1)%maxSize 。10 .無論是順序棧還是順序隊列，插入元素時必須先進行棧或隊列是否為滿的判斷,刪除元素時必須先進行棧或隊列是否為空的判斷;而鏈棧或鏈隊列中，插入元素無需進行棧或隊列是否為滿的判斷，只要在刪除元素時先進行棧或隊列是否為空的 判斷。三、算法設計題1. 編寫一個函數，要求借助一個棧把一個數組中的數據元素逆置。參考答案：/借助一個順序棧將已知一個數組中的數據元素逆置pu

8、blic reverse(Object 口 a) throws Exception SqStack S=new SqStack(a.length);/構造一個容量為 a.length的順序棧for(int i=0;i<a.length;i+) S.push(ai);for( int i=0;i<a.length;i+) ai尸S.pop();2. 編寫一個函數判斷一個字符序列是否為回文序列，所謂回文序列就是正讀與反讀都相同的字符序列，例如： abba和abdba均是回文序列。要求只使用棧來實現。參考答案：判斷字符序列是否為回文序列，若是則返回true值，否則返回false 。pub

9、lic boolean isPalindSeq(String str) LinkStack S = new LinkStack();int i = 0;for (; i < str.length(); i+) S.push(str.charAt(i);for (i = 0;i< str.length(); i+) char c = (Character) S.pop().charValue();if (c != str.charAt(i) return false; return true;3. 假設以一個數組實現兩個棧：一個棧以數組的第一個存儲單元作為棧底，另一個棧以數組的最后一

10、個存儲單元作為棧底, 這種棧稱為順序雙向棧。 試編寫一個順序雙向棧類DuSqStack ， 類中要求編寫 3 個方法。 一個是構造方法 DuDuSqStack(int maxSize), 此方法實現構造一個容量為 maxSize 的順序雙向空棧；一個是實現入棧操作的方法push(Object X,int i),此方法完成將數據元素X壓入到第i(i=0或1)號棧中的操作；一個是實現出棧操作的方法pop( int i), 此方法完成將第 i 號棧的棧頂元素出棧的操作。參考答案 :class DuSqStackprivate int top0; / private int top1; / priva

11、te int base0;/ private int base1;/private Object stackElem; /棧存儲空間棧頂指針 , 指示第 0 號的棧頂元素的下一個位置棧頂指針,指示第1號的棧頂元素的下一個位置棧尾指針,指示第0號的棧底元素棧尾指針,指示第1號的棧底元素/ 構造方法public DuSqStack(int maxSize) / 初始化棧 , 即構造一個雙向空棧為棧分配 maxSize 個存儲單元stackElem = new ObjectmaxSize;/top0=base0=0;top1=base1=maxSize-1;/ 入棧操作方法public void p

12、ush(Object X, int i) throws Exception /將數據元素X壓入到第i(i的值為0或1)號棧中if (top0 > top1) /棧滿throw new Exception(" 棧已滿 ");/ 拋出異常else if (i=0)stackElemtop0+=X;else if (i=1)stackElemtop1-=X;/ 出棧操作方法public Object pop(int i) throws Exception / 將 S 中第 i 號棧的棧頂元素出棧, 并返回棧頂元素值Object x=null;if(i=0)if (top0=

13、base0)throw new Exception("第 0 號棧為空 ");elsex=stackElem-top0;else if (i=1)if (top1=base1)throw new Exception("第 0 號棧為空 ");elsex=stackElem+top1;return x; / DuSqStack 類結束4. 循環順序隊列類采用設置一個計數器的方法來區分循環隊列的判空和判滿。 試分別編寫順序循環隊列中入隊和出隊操作的函數。參考答案 :/ 循環順序隊列存儲結構類描述如下 :class CircleSqQueue_num priv

14、ate Object queueElem; / 隊列存儲空間private int front; / 隊首的引用，若隊列不空，指向隊首元素，初值為 0private int rear;/ 隊尾的引用，若隊列不空，指向隊尾元素的下一個位置, 初值為 0private int num;/ 計數器用來記錄隊列中的數據元素個數 / CircleSqQueue_num 類結束為類 CircleSqQueue_num 所編寫的入隊和出隊操作方法如下：/ 入隊操作方法把指定的元素x 插入隊列輸出異常更改隊尾的位置public void offer(Object x) throws Exception /if

15、 (num=queueElem.length)/ 隊列滿throw new Exception(" 隊列已滿 ");/ else / 隊列未滿queueElemrear = x;/ x 加入隊尾rear=(rear + 1) % queueElem.length; /+num; /計數器加 1/ 出隊操作方法public Object poll() / 移除隊首元素并作為此函數的值返回該對象，如果此隊列為空，則返回 nullif (num=0)/ 隊列為空return null;else Object t = queueElemfront;/取出隊首元素front = (f

16、ront + 1) % queueElem.length;/更改隊首的位置-num; /計數器減1return t;/返回隊首元素，試編寫相5. 假設采用帶頭結點的循環鏈表來表示隊列，并且只設一個指向隊尾元素的指針(不設隊首指針)應的隊列置空、隊列判空、入隊和出隊操作的函數。參考答案 :用隊尾指針標識的循環鏈隊列的類描述如下 :class CircleLinkQueue private Node rear;/循環鏈隊列的尾指針為此類編寫的隊列置空、隊列判空、入隊和出隊操作的方法分別如下：/隊列置空操作方法 public void clear() /將一個已經存在的帶頭結點的循環鏈隊列置成空隊列 rear.setNext(rear);/入隊操作方法public void offer ( Object x) throws Exception 將指定的元素x插入到帶頭結點的循環鏈隊列中Node p= new Node(x); /生成新結點p.setNext(rear.getNext();/插入鏈列歹 U 的尾部