第3章-棧與隊(duì)列習(xí)題參考答案

1、習(xí)題三參考答案?jìng)渥ⅲ杭t色字體標(biāo)明的是與書本內(nèi)容有改動(dòng)的內(nèi)容、選擇題1 .在棧中存取數(shù)據(jù)的原則是（B ）。A.先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.沒有限制2 .若將整數(shù)1、2、3、4依次進(jìn)棧，則不可能得到的出棧序列是（ D ）。A. 1234 B. 1324 C. 4321 D. 14233 .在鏈棧中，進(jìn)行出棧操作時(shí)（ B ）。A.需要判斷棧是否滿B.需要判斷棧是否為空C.需要判斷棧元素的類型D.無(wú)需對(duì)棧作任何差別4.在順序棧中，若棧頂指針判空條件是（A ）。top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxSize,貝U順序棧的A . top=0 B.top=-1C. top=m

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

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

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

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

6、Next(); 。6 .隊(duì)列也是一種操作受限的線性表，它與棧不同的是，隊(duì)列中所有的插入操作均限制在表的一端進(jìn)行，而所有 的刪除操作都限制在表的另一端進(jìn)行，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。隊(duì)列具有先進(jìn)先出的特點(diǎn)。7 .由于隊(duì)列的刪除和插入操作分別在隊(duì)首和隊(duì)尾進(jìn)行，因此，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)描述中分別需要設(shè)置兩個(gè)指針分別指向隊(duì)首結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)，這兩個(gè)指針又分別稱為 隊(duì)首指針和隊(duì)尾指針。8 .循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過數(shù)學(xué)上的求模(或取余)運(yùn)算來(lái)實(shí)現(xiàn)的。9 .在循環(huán)順序隊(duì)列中，若規(guī)定當(dāng) front=rear 時(shí)，循環(huán)隊(duì)列為空；當(dāng) fron

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

8、blic reverse(Object 口 a) throws Exception SqStack S=new SqStack(a.length);/構(gòu)造一個(gè)容量為 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. 編寫一個(gè)函數(shù)判斷一個(gè)字符序列是否為回文序列，所謂回文序列就是正讀與反讀都相同的字符序列，例如： abba和abdba均是回文序列。要求只使用棧來(lái)實(shí)現(xiàn)。參考答案：判斷字符序列是否為回文序列，若是則返回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. 假設(shè)以一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧：一個(gè)棧以數(shù)組的第一個(gè)存儲(chǔ)單元作為棧底，另一個(gè)棧以數(shù)組的最后一

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

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

12、ush(Object X, int i) throws Exception /將數(shù)據(jù)元素X壓入到第i(i的值為0或1)號(hào)棧中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 號(hào)棧的棧頂元素出棧, 并返回棧頂元素值Object x=null;if(i=0)if (top0=

13、base0)throw new Exception("第 0 號(hào)棧為空 ");elsex=stackElem-top0;else if (i=1)if (top1=base1)throw new Exception("第 0 號(hào)棧為空 ");elsex=stackElem+top1;return x; / DuSqStack 類結(jié)束4. 循環(huán)順序隊(duì)列類采用設(shè)置一個(gè)計(jì)數(shù)器的方法來(lái)區(qū)分循環(huán)隊(duì)列的判空和判滿。 試分別編寫順序循環(huán)隊(duì)列中入隊(duì)和出隊(duì)操作的函數(shù)。參考答案 :/ 循環(huán)順序隊(duì)列存儲(chǔ)結(jié)構(gòu)類描述如下 :class CircleSqQueue_num priv

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

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

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