1、3.5習題一、名詞解釋棧棧是限制在表的一端進行插入和刪除操作的線性表。允許插入、刪除的這一端稱為棧頂，另一個固定端稱為棧底。棧的順序結構：利用順序存儲方式實現的棧稱為順序棧。棧的鏈式結構：用鏈式存儲結構實現的棧稱為鏈棧。隊隊是一種“先進先出” (FIFO-First In First Out)的數據結構，即插入操 作在表一端進行，而刪除操作在表的另一端進行，這種數據結構稱為隊列。 把允許插入的一端稱為隊尾(rear)，把允許刪除的一端稱為隊頭(front)。隊的順序結構：順序存儲的隊稱為順序隊。隊的鏈式結構：采用鏈式存儲結構的隊稱為鏈隊。二、判斷題棧和隊列都是特殊的線性表。 (V )棧和隊列都

2、將插入和刪除操作限制在表的端點處進行。(V )只允許在表的一端進行插入和刪除操作的線性表稱為棧。(V)沒有元素的棧稱為空棧，空棧用不著棧頂指針。(X ) TOC o 1-5 h z 只要棧不空，就能任意刪除棧的元素。(X )棧允許刪除的一端稱為棧頂，而棧底元素是不能刪除的。(X )對采用鏈式存儲結構的棧進行操作不必判斷溢出。(V )元素進出隊列一定滿足“先進先出”的規律。(V )鏈隊列不存在溢出問題。 (V )在鏈隊列中刪除一個元素是在鏈表的最前端進行的。(V )三、單項選擇題棧和隊列的共同之處在于它們具有相同的(A )。邏輯特性B.物理特性C.運算方法 D.元素類型棧和隊列都是特殊的線性表，

3、其特殊性在于(C )。它們具有一般線性表所沒有的邏輯特性它們的存儲結構比較特殊對它們的使用方法做了限制它們比一般線性表更簡單若5個元素的出棧序列為1, 2, 3, 4, 5,則進棧序列可能是()。2, 4, 3, 1, 5 B. 2, 3, 1, 5, 4C.3,1,4,2,5D.3,1,2,5,4某隊列初始為空，若它的輸入序列為a, b,c,d,它的輸出序列應為()。A. a, b, c, dB. d, c, b, aC. a, c, b, dD. d, a, c, b當3個元素的進棧序列給定以后，由這3個元素組成的可能的出棧序列應該有()。A. 5種 B. 6種 C. 4種 D. 3種若棧

4、采用順序存儲結構，正常情況下，往堆棧中插入一個元素，棧頂 指針top的變化是()。A.不變 B. top=0 C. -topD. top+若棧采用順序存儲結構，正常情況下，刪除棧中一個元素，棧頂指 針top的變化是()。A.不變 B. top=0 C. top-D. top+若隊列采用順序存儲結構，元素的排列順序(B )。與元素的值的大小有關由元素進入隊列的先后順序決定與隊頭指針和隊尾指針的取值有關n與作為順序存儲結構的數組的大小有關若非空棧采用含頭結點的鏈式存儲結構，棧頂指針為top,刪除堆棧的 一個元素的過程是依次執行：p=top，( B ), free(p)。A. top=p-nextC

5、.p=toptop-next =p-nextp=p- next若隊列采用鏈式存儲結構，隊頭元素指針與隊尾元素指針分別為 front和rear，向隊列中插入一個由p所指的新結點的過程是依次執行：(), rear二p。A. rear=pB. front=prear-next=pD. front-next=p若非空隊列采用鏈式存儲結構，隊頭元素指針與隊尾元素指針分別為front和rear，刪除隊列的一個元素的過程是依次執行：p=front,(),free(p)。A.rear=pB.rear=p-nextC.rear=p-nextD.front=p-next在循環隊列中，若front與rear分別表示

6、隊頭元素和隊尾元素的位 置，則判斷循環隊列隊空的條件是(C )。A. front=rear+1B. rear=front+1C.front=rear D.rear=front-1四、填空題棧和隊列的邏輯結構都是一線性 結構。棧的插入和刪除操作都是在 棧頂 進行，而隊列的插入操作在 隊尾 進行，刪除操作在隊頭進行。對某棧執行刪除操作時，只有在棧中只有一個元素的情況下，才 會將棧底元素刪除。在具體的程序設計過程中，棧的順序存儲結構一般是利用一個數組 描述的，同時還要定義一個整型變量來給出棧頂元素的位置。若棧采用順序存儲結構，在不產生溢出的情況下 往 棧中插人一 個新元素，首先將棧頂指針后移一個位置

7、 ，然后 將被插入元素放在修改后 的棧頂指針所指出的位置若隊列采用順序存儲結構，未溢出時插入一個元素首先一將隊尾指針 后移一個位置，然后再 將被插入元素放在修改后的隊尾指針所指出的位置當棧的最大長度難以估計時，最好采用鏈式存儲結構。五、綜合應用題（1）已知棧采用鏈式存儲結構，初始時為空，請畫出a,b,c, d四個元素 依次進棧以后該棧的狀態，然后再畫出此時的那個棧頂元素出棧后棧的狀態。（2）若按從左到右的順序依次讀人已知序列a，b，c，d，e，f，g中的元 素，然后結合棧操作，能得到下列序列中的哪些序列（每個元素進棧一次，下列 序列表示出棧的次序）？A.d，e，c，f，b，g，a B.f，e，g，d，a，c，bC.e，f，d，g，b，c，a D.c，d，b，e，f，a，g答：A、D滿足出棧序列。滿足A出棧次序的具體操作序列為：a,b,c,d進