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

1、習(xí)題三參考答案習(xí)題三參考答案備注備注:紅色字體標(biāo)明的是與書本內(nèi)容有改動的內(nèi)容。紅色字體標(biāo)明的是與書本內(nèi)容有改動的內(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）。A1234B.1324C.4321D.14233在鏈棧中，進(jìn)行出棧操作時(shí)（B）。A需要判斷棧是否滿B.需要判斷棧是否為空C.需要判斷棧元素的類型D.無需對棧

2、作任何差別4在順序棧中，若棧頂指針top指向棧頂元素的下一個存儲單元，且順序棧的最大容量是maxSize，則順序棧的判空條件是（A）。Atop==0B.top==1C.top==maxSizeD.top==maxSize15在順序棧中，若棧頂指針top指向棧頂元素的下一個存儲單元，且順序棧的最大容量是maxSize。則順序棧的判滿的條件是（C）。Atop==0B.top==1C.top==maxSizeD.top==maxSize16在

3、隊(duì)列中存取數(shù)據(jù)元素的原則是（A）。A先進(jìn)先出B.先進(jìn)后出C.后進(jìn)后出D.沒有限制7在循環(huán)順序隊(duì)列中，假設(shè)以少用一個存儲單元的方法來區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個存儲單元，隊(duì)列的最大存儲容量為maxSize，則隊(duì)列的判空條件是（A）。Afront==rearB.front!=rearC.front==rear1D.front==(rear1)%maxSize8在循

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

5、ear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個存儲單元，隊(duì)列的最大存儲容量為maxSize，則隊(duì)列的長度是（C）。ArearfrontB.rearfront1C.(rearfrontmaxSize)%maxSizeD.(rearfront1)%maxSize10.設(shè)長度為n的鏈隊(duì)列采用單循環(huán)鏈表加以表示，若只設(shè)一個頭指針指向隊(duì)首元素，則入隊(duì)操作的時(shí)間復(fù)雜度為（B）。AO(1)BO(n)CO(log2n)DO(n2)二

6、、填空題二、填空題1.棧是一種操作受限的特殊線性表，其特殊性體現(xiàn)在其插入和刪除操作都限制在表尾進(jìn)行。允許插入和刪除操作的一端稱為棧頂，而另一端稱為棧底。棧具有后進(jìn)先出的特點(diǎn)。2.棧也有兩種存儲結(jié)構(gòu)，一種是順序存儲，另一種是鏈?zhǔn)酱鎯?；以這兩種存儲結(jié)構(gòu)存儲的棧分別稱為順序棧和鏈棧。3.在順序棧中，假設(shè)棧頂指針top是指向棧頂元素的下一個存儲單元，則順序棧判空的條件是top==0棧頂3.假設(shè)以一個數(shù)組實(shí)現(xiàn)兩個棧：一個棧以數(shù)組的第一個存儲單元作

7、為棧底，另一個棧以數(shù)組的最后一個存儲單元作為棧底這種棧稱為順序雙向棧。試編寫一個順序雙向棧類DuSqStack，類中要求編寫3個方法。一個是構(gòu)造方法DuDuSqStack(intmaxSize)此方法實(shí)現(xiàn)構(gòu)造一個容量為maxSize的順序雙向空棧；一個是實(shí)現(xiàn)入棧操作的方法push(ObjectXinti)此方法完成將數(shù)據(jù)元素X壓入到第i(i=0或1)號棧中的操作；一個是實(shí)現(xiàn)出棧操作的方法pop（inti)此方法完成將第i號棧的棧頂元素出

8、棧的操作。參考答案參考答案:classDuSqStackprivateObject[]stackElem棧存儲空間privateinttop0棧頂指針指示第0號的棧頂元素的下一個位置privateinttop1棧頂指針指示第1號的棧頂元素的下一個位置privateintbase0棧尾指針指示第0號的棧底元素privateintbase1棧尾指針指示第1號的棧底元素構(gòu)造方法構(gòu)造方法publicDuSqStack(intmaxSize)初始

9、化棧即構(gòu)造一個雙向空棧stackElem=newObject[maxSize]為棧分配maxSize個存儲單元top0=base0=0top1=base1=maxSize1入棧操作方法入棧操作方法publicvoidpush(ObjectXinti)throwsException將數(shù)據(jù)元素X壓入到第i(i的值為0或1)號棧中if(top0top1)棧滿thrownewException(“棧已滿“)拋出異常elseif(i==0)sta

10、ckElem[top0]=Xelseif(i==1)stackElem[top1]=X出棧操作方法出棧操作方法publicObjectpop(inti)throwsException將S中第i號棧的棧頂元素出棧并返回棧頂元素值Objectx=nullif(i==0)if(top0==base0)thrownewException(“第0號棧為空“)elsex=stackElem[top0]elseif(i==1)if(top1==bas