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

習(xí)題三參考答案?jìng)渥?紅色字體標(biāo)明的是與書本內(nèi)容有改動(dòng)的內(nèi)容。一、選擇題在棧中存取數(shù)據(jù)的原則是（B）。先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.沒(méi)有限制2．若將整數(shù)1、2、3、4依次進(jìn)棧，則不可能得到的出棧序列是（D）。A．1234B.1324C.4321D.14233．在鏈棧中，進(jìn)行出棧操作時(shí)（B）。A．需要判斷棧是否滿B.需要判斷棧是否為空C.需要判斷棧元素的類型D.無(wú)需對(duì)棧作任何差別4．在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxSize，則順序棧的判空條件是（A）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-15．在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxSize。則順序棧的判滿的條件是（C）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-16．在隊(duì)列中存取數(shù)據(jù)元素的原則是（A）。A．先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.沒(méi)有限制7．在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判空條件是（A）。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和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的長(zhǎng)度是（C）。A．rear-frontB.rear-front+1C.(rear-front+maxSize)%maxSizeD.(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)二、填空題棧是一種操作受限的特殊線性表，其特殊性體現(xiàn)在其插入和刪除操作都限制在表尾進(jìn)行。允許插入和刪除操作的一端稱為棧頂，而另一端稱為棧底。棧具有后進(jìn)先出的特點(diǎn)。棧也有兩種存儲(chǔ)結(jié)構(gòu)，一種是順序存儲(chǔ)，另一種是鏈?zhǔn)酱鎯?chǔ)；以這兩種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的棧分別稱為順序棧和鏈棧。在順序棧中，假設(shè)棧頂指針top是指向棧頂元素的下一個(gè)存儲(chǔ)單元，則順序棧判空的條件是top==0;棧頂元素的訪問(wèn)形式是stackElem[top-1];在不帶表頭結(jié)點(diǎn)的鏈棧中，若棧頂指針top直接指向棧頂元素，則將一個(gè)新結(jié)點(diǎn)p入棧時(shí)修改鏈的兩個(gè)對(duì)應(yīng)語(yǔ)句為p.setNext(top)；top=p;。在不帶表頭結(jié)點(diǎn)的鏈棧中，若棧頂指針top直接指向棧頂元素，則棧頂元素出棧時(shí)的修改鏈的對(duì)應(yīng)語(yǔ)句為top=top.getNext();。隊(duì)列也是一種操作受限的線性表，它與棧不同的是，隊(duì)列中所有的插入操作均限制在表的一端進(jìn)行，而所有的刪除操作都限制在表的另一端進(jìn)行，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)首。隊(duì)列具有先進(jìn)先出的特點(diǎn)。由于隊(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ì)尾指針。循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過(guò)數(shù)學(xué)上的求模（或取余）運(yùn)算來(lái)實(shí)現(xiàn)的。在循環(huán)順序隊(duì)列中，若規(guī)定當(dāng)front==rear時(shí)，循環(huán)隊(duì)列為空；當(dāng)front==(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。無(wú)論是順序棧還是順序隊(duì)列，插入元素時(shí)必須先進(jìn)行?；蜿?duì)列是否為滿的判斷，刪除元素時(shí)必須先進(jìn)行?；蜿?duì)列是否為空的判斷；而鏈?；蜴滉?duì)列中，插入元素?zé)o需進(jìn)行?；蜿?duì)列是否為滿的判斷，只要在刪除元素時(shí)先進(jìn)行?；蜿?duì)列是否為空的判斷。三、算法設(shè)計(jì)題編寫一個(gè)函數(shù)，要求借助一個(gè)棧把一個(gè)數(shù)組中的數(shù)據(jù)元素逆置。參考答案://借助一個(gè)順序棧將已知一個(gè)數(shù)組中的數(shù)據(jù)元素逆置publicreverse(Object[]a)throwsException{SqStackS=newSqStack(a.length);//構(gòu)造一個(gè)容量為a.length的順序棧for(inti=0;i<a.length;i++)S.push(a[i]);for(inti=0;i<a.length;i++)a[i]=S.pop();}編寫一個(gè)函數(shù)判斷一個(gè)字符序列是否為回文序列，所謂回文序列就是正讀與反讀都相同的字符序列，例如：abba和abdba均是回文序列。要求只使用棧來(lái)實(shí)現(xiàn)。參考答案://判斷字符序列是否為回文序列,若是則返回true值,否則返回false。publicbooleanisPalindSeq(Stringstr){ LinkStackS=newLinkStack(); inti=0; for(;i<str.length();i++) S.push(str.charAt(i)); for(i=0;i<str.length();i++){ charc=((Character)S.pop()).charValue(); if(c!=str.charAt(i)) returnfalse; } returntrue; privateNoderear;//循環(huán)鏈隊(duì)列的尾指針……}為此類編寫的隊(duì)列置空、隊(duì)列判空、入隊(duì)和出隊(duì)操作的方法分別如下：//隊(duì)列置空操作方法 publicvoidclear(){//將一個(gè)已經(jīng)存在的帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)列置成空隊(duì)列 rear.setNext(rear); } //入隊(duì)操作方法 publicvoidoffer(Objectx)throwsException{ //將指定的元素x插入到帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)列中Nodep=newNode(x);//生成新結(jié)點(diǎn)p.setNext(rear.getNext());//插入鏈列列的尾部rear.setNext(p);rear=p; } //出隊(duì)操作方法 publicvoidpoll()throwsException{//移除帶頭結(jié)點(diǎn)的循環(huán)鏈隊(duì)列中的隊(duì)首元素并作為此函數(shù)的值返回該對(duì)象，如果此隊(duì)列為空，則返回null Node