棧和隊(duì)列(參考答案)

1、第3章 棧和隊(duì)列（參考答案）一、填空題 1.線性表、棧和隊(duì)列都是 線性 結(jié)構(gòu)，可以在線性表的 任意 位置插入和刪除元素；對(duì)于棧只能在 棧頂 插入和刪除元素；對(duì)于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)頭 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為 棧頂 不允許插入和刪除運(yùn)算的一端稱為 棧底 。3. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。4. 在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的當(dāng)前位置。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有 n-1 個(gè)元素。6. 向棧中壓入元素的操作(棧頂指針指向當(dāng)前棧頂元素的下一位置)是先 存入元素 ，后 移動(dòng)棧

2、頂指針 。7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是 先 取出元素 ，后 移動(dòng)隊(duì)首指針 。二、判斷正誤（ ）1. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類(lèi)型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類(lèi)型。 （ ）2. 在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。 （ ）3. 棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。（ ）4. 對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。 （ ）5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 （ ）6. 棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 （ ）7. 棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。 （ ）8. 兩個(gè)棧共享一片

3、連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 （ ）9. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。（ ）10. 一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。 三、單項(xiàng)選擇題（ B ）1.棧中元素的進(jìn)出原則是先進(jìn)先出 后進(jìn)先出 ?？談t進(jìn) 棧滿則出（ C ）2.若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為i n-i n-i+1 不確定（ B ）3.判定一個(gè)棧ST（最多元素為m0）為空的條件是ST-top!=0 ST-top=0 ST-top!=m0

4、 ST-top=m0（ A ）4.判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是QU-rear QU-front = = m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ D ）5數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為（）rf; （）（nfr）% n; （）nrf; （）（nrf）% n6. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和

5、a4，對(duì)他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?；蜻M(jìn)隊(duì)操作時(shí)，按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)棧或隊(duì)的初始狀態(tài)都是空?，F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次，出棧一次，再進(jìn)棧兩次，出棧一次；這時(shí)，第一次出棧得到的元素是 A ，第二次出棧得到的元素是 B 是；類(lèi)似地，考慮對(duì)這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次，出隊(duì)一次，再進(jìn)隊(duì)兩次，出隊(duì)一次；這時(shí)，第一次出隊(duì)得到的元素是 C ，第二次出隊(duì)得到的元素是 D 。經(jīng)操作后，最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案：AD：a1 a2 a3 a4E： 1 2 3 0答：ABCDE2, 4, 1, 2, 27.從供選擇的答案中，選出應(yīng)填入下面敘述 ？

6、 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。棧是一種線性表，它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A1,n來(lái)表示一個(gè)棧，An為棧底，用整型變量T指示當(dāng)前棧頂位置，AT為棧頂元素。往棧中推入（PUSH）一個(gè)新元素時(shí)，變量T的值 B ；從棧中彈出（POP）一個(gè)元素時(shí)，變量T的值 C 。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過(guò)PUSH，POP，PUSH，PUSH，POP操作后，從棧中彈出的元素的序列是 D ，變量T的值是 E 。供選擇的答案：A： 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B，C： 加1 減1 不變 清0 加2 減2D： a,b b,c c,ab,a c,b a,cE： n+1 n+

7、2 n n-1 n-2答案：ABCDE=2, 2, 1, 6, 48.從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否 A ；在做退棧運(yùn)算時(shí)，應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說(shuō)明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性，由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端，這樣，只有當(dāng) E 時(shí)，才產(chǎn)生上溢。供選擇的答案：A，B：空 滿 上溢 下溢C： n-1 n n+1 n/2D： 長(zhǎng)度 深度 棧頂 棧底E：兩個(gè)棧的棧頂同時(shí)到達(dá)棧空間的中心點(diǎn)

8、 其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn) 兩個(gè)棧的棧頂在達(dá)?？臻g的某一位置相遇 兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案：ABCDE2, 1, 2, 4, 3四、簡(jiǎn)答題1.說(shuō)明線性表、棧與隊(duì)的異同點(diǎn)。答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特殊的線性表，即受限的線性表，只是對(duì)插入、刪除運(yùn)算加以限制。不同點(diǎn)：運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。 用途不同，堆棧用于子程調(diào)用和保護(hù)現(xiàn)場(chǎng)，隊(duì)列用于多道作業(yè)處理、指令寄

9、存及其他運(yùn)算等等。2.設(shè)有編號(hào)為1，2，3，4的四輛列車(chē)，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車(chē)站，具體寫(xiě)出這四輛列車(chē)開(kāi)出車(chē)站的所有可能的順序。答：至少有14種。 全進(jìn)之后再出情況，只有1種：4，3，2，1 進(jìn)3個(gè)之后再出的情況，有3種，3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況，有5種，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個(gè)之后再出的情況，有5種，1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，abba和abcba是回文，abcde 和ababab

10、則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j-）從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。哪種方式最好，要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_(kāi)到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。（但堆棧是先減后壓還是）若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開(kāi)輔助空間，可以從鏈?zhǔn)组_(kāi)始入棧，全部壓入后再依次輸出。4.順序隊(duì)的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？答：一般的一維數(shù)組隊(duì)列的尾指針已

11、經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三：設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空。使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）。我們常采用法，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲?，而另一個(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是： f=rear 隊(duì)滿標(biāo)志是：f=(r+1)%N5.設(shè)循環(huán)隊(duì)列的容量為40（序號(hào)從0到39），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有 front=11，rear=19; front=19，rear=11；問(wèn)在這兩種情況下，循環(huán)隊(duì)列中各有元素

12、多少個(gè)？答：用隊(duì)列長(zhǎng)度計(jì)算公式： (Nrf)% N L=（401911）% 40=8 L=（401119）% 40=32五、閱讀理解1. 寫(xiě)出下列程序段的輸出結(jié)果（棧的元素類(lèi)型SElem Type為char）。void main( )Stack S;Char x,y;InitStack(S);X=c;y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);答：輸出為“stac

13、k”。2. 寫(xiě)出下列程序段的輸出結(jié)果（隊(duì)列中的元素類(lèi)型QElem Type為char）。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答：輸出為“char”。3. 簡(jiǎn)述以下算法的功能（棧和隊(duì)列的元素類(lèi)型均為int）。voi

14、d algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素進(jìn)行逆置。六.算法設(shè)計(jì)題#define maxSize 5void InOuts() int smaxSize; int top=0; int x; do scanf(%d,&x); if(x!=-1) if(top=maxSize) printf(棧滿);break;

15、else stop+=x; while(x!=-1); while(top0) printf(%d ,s-top); /*/*第2題*/*2.設(shè)有兩個(gè)棧S1,S2 都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)O.maxsize-1,為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S1,S2 有關(guān)入棧和出棧的操作算法。*/#define maxSize 100typedef struct stk int stackmaxSize; /棧空間 int top2; /top為兩個(gè)棧頂指針;stk s;void init() /初始化 s.top0=-1; s.top1=maxSize;/入棧/i為棧號(hào)，1為右棧，0為左棧，x為入棧元素/返回1成功，-1為失敗，0為棧滿int Push(int i,int x) if(i1) printf(棧號(hào)輸入不正確n);return -1; if(s.top1-s.top0=1) printf(棧已滿n);return 0; switch(i) case 0: s.stack+s.top0=x;break; case 1: s.stack-s.top1=x;break; return 1;/出棧/i為棧號(hào)，1