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

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

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

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

4、以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為 列的長(zhǎng)度是（C ）oA. rear-frontB. rear-front+1C. （rear-fr on t+maxSize）%maxSize D. （rear-fr on t+1）%maxSize10. 設(shè)長(zhǎng)度為n的鏈隊(duì)列采用單循環(huán)鏈表加以表示，若只設(shè)一個(gè)頭指針指向隊(duì)首元素，則入隊(duì)操作的時(shí)間復(fù)雜度為(B )。2A . 0(1)B . 0(n) C. O(log 2n)D . 0(n )二、填空題表尾 進(jìn)行。允許插入和刪除1. 棧是一種操作受限的特殊線性表，其特

5、殊性體現(xiàn)在其插入和刪除操作都限制在操作的一端稱為棧頂，而另一端稱為 棧底。棧具有后進(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 ;棧頂元素的訪問(wèn)形式是 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直接指向棧頂元素，則棧頂元素出

6、棧時(shí)的修改鏈的對(duì)應(yīng)語(yǔ)句為top=top.getNext(); 。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è)指針?lè)謩e指向隊(duì)首結(jié)點(diǎn)和隊(duì)尾結(jié)點(diǎn)，這兩個(gè)指針又分別稱為隊(duì)首指針和隊(duì)尾指廠8. 循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過(guò)數(shù)學(xué)上的求模(或取余)運(yùn)算來(lái)實(shí)現(xiàn)的。9. 在循環(huán)順序隊(duì)列中，若規(guī)定當(dāng)fron t=

7、rear時(shí)，循環(huán)隊(duì)列為空；當(dāng)fron t=(rear+1)%maxSize時(shí)，循環(huán)隊(duì)列為滿，則入隊(duì)操作時(shí)的隊(duì)尾指針變化的相應(yīng)語(yǔ)句是rear=(rear+1)% maxSize ;出隊(duì)操作時(shí)的隊(duì)首指針變化的相應(yīng)語(yǔ)句是 fron t=(fro nt+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. 編寫(xiě)一個(gè)函數(shù)，要求借助一個(gè)棧把一個(gè)數(shù)組中的數(shù)據(jù)元素逆置。參考答案：/借助一個(gè)順序棧

8、將已知一個(gè)數(shù)組中的數(shù)據(jù)元素逆置public reverse(Object a) throws Excepti on SqStack S=new SqStack(a.le ngth); /構(gòu)造一個(gè)容量為 a.le ngth 的順序棧for(i nt i=0;ia .len gth;i+)S.push(ai);for( in t i=0;ia.le ngth;i+) ai=S.pop();2. 編寫(xiě)一個(gè)函數(shù)判斷一個(gè)字符序列是否為回文序列，所謂回文序列就是正讀與反讀都相同的字符序列，例如： abba和abdba均是回文序列。要求只使用棧來(lái)實(shí)現(xiàn)。參考答案：/判斷字符序列是否為回文序列，若是則返回tru

9、e值，否則返回false。public boolea n isPali ndSeq(Stri ng str) Li nkStack S = new Lin kStack();int i = 0;for (; i str.le ngth(); i+)S.push(str.charAt(i);for (i = 0; i top1) /棧滿throw new Exception( 棧已滿 );/ 拋出異常 else if (i=0)stackElemtop0+=X;else if (i=1)stackElemtop1-=X;/ 出棧操作方法 public Object pop(int i) thro

10、ws Exception /將S中第i號(hào)棧的棧頂元素出棧，并返回棧頂元素值Object x=null;if(i=0)if (top0=base0)throw new Exception(第 0 號(hào)棧為空 );elsex=stackElem-top0;else if (i=1)if (top1=base1)第 0 號(hào)棧為空 );throw new Exception( elsex=stackElem+top1;return x; / DuSqStack 類結(jié)束試分別編寫(xiě)順序循環(huán)隊(duì)列中入隊(duì)4. 循環(huán)順序隊(duì)列類采用設(shè)置一個(gè)計(jì)數(shù)器的方法來(lái)區(qū)分循環(huán)隊(duì)列的判空和判滿。 和出隊(duì)操作的函數(shù)。參考答案 :/ 循

11、環(huán)順序隊(duì)列存儲(chǔ)結(jié)構(gòu)類描述如下 :class CircleSqQueue_num private Object queueElem; / private int front;private int rear;private int num;/隊(duì)列存儲(chǔ)空間隊(duì)首的引用，若隊(duì)列不空，指向隊(duì)首元素，初值為 隊(duì)尾的引用，若隊(duì)列不空，指向隊(duì)尾元素的下一個(gè)位置 計(jì)數(shù)器用來(lái)記錄隊(duì)列中的數(shù)據(jù)元素個(gè)數(shù)0, 初值為 0 / CircleSqQueue_num 類結(jié)束為類 CircleSqQueue_num 所編寫(xiě)的入隊(duì)和出隊(duì)操作方法如下： / 入隊(duì)操作方法public void offer(Object x) thr

12、ows Exception /把指定的元素 x 插入隊(duì)列if (num=queueElem.length)/隊(duì)列滿throw new Exception(隊(duì)列已滿 );/輸出異常else / 隊(duì)列未滿queueElemrear = x;/ x加入隊(duì)尾rear=(rear + 1) % queueElem.length; /更改隊(duì)尾的位置+num; / 計(jì)數(shù)器加 1/ 出隊(duì)操作方法 public Object poll() / 移除隊(duì)首元素并作為此函數(shù)的值返回該對(duì)象，如果此隊(duì)列為空，則返回 null if (num=0)/ 隊(duì)列為空return null;else Object t = queu

13、eElemfront;/取出隊(duì)首元素front = (front + 1) % queueElem.length;/ 更改隊(duì)首的位置-num; / 計(jì)數(shù)器減 1 return t;/ 返回隊(duì)首元素，試編寫(xiě)相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 CircleL in kQueue private Node rear;/循環(huán)鏈隊(duì)列的尾指針為此類編寫(xiě)的隊(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 Excepti on /將指定的元素x插入到帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)列中Node p= new Node(x); /生成新結(jié)點(diǎn)p.setNext(rear.getNext();插入鏈列列的尾部rear.setNext(p);rear=p;/出隊(duì)操作方法nullpublic