第3章-棧與隊列習題參考答案

1、習題三參考答案習題三參考答案備注備注:紅色字體標明的是與書本內容有改動的內容。紅色字體標明的是與書本內容有改動的內容。一、選擇題一、選擇題1.在棧中存取數據的原則是（B）。A先進先出B.先進后出C.后進后出D.沒有限制2若將整數1、2、3、4依次進棧，則不可能得到的出棧序列是（D）。A1234B.1324C.4321D.14233在鏈棧中，進行出棧操作時（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、隊列中存取數據元素的原則是（A）。A先進先出B.先進后出C.后進后出D.沒有限制7在循環(huán)順序隊列中，假設以少用一個存儲單元的方法來區(qū)分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的判空條件是（A）。Afront==rearB.front!=rearC.front==rear1D.front==(rear1)%maxSize8在循

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

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

6、、填空題二、填空題1.棧是一種操作受限的特殊線性表，其特殊性體現在其插入和刪除操作都限制在表尾進行。允許插入和刪除操作的一端稱為棧頂，而另一端稱為棧底。棧具有后進先出的特點。2.棧也有兩種存儲結構，一種是順序存儲，另一種是鏈式存儲；以這兩種存儲結構存儲的棧分別稱為順序棧和鏈棧。3.在順序棧中，假設棧頂指針top是指向棧頂元素的下一個存儲單元，則順序棧判空的條件是top==0棧頂3.假設以一個數組實現兩個棧：一個棧以數組的第一個存儲單元作

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

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

9、化棧即構造一個雙向空棧stackElem=newObject[maxSize]為棧分配maxSize個存儲單元top0=base0=0top1=base1=maxSize1入棧操作方法入棧操作方法publicvoidpush(ObjectXinti)throwsException將數據元素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