Q15.
X、Y、Z，三個符號依序壓入(Push)到堆疊(Stack)中，壓入過程中，在堆疊內的元素可隨時彈出(Pop)堆疊，下列的輸出中，何者不可能由堆疊中產生出來？
電腦軟體設計共同科目 · 乙級 · Q15
難易度分析
3 / 5
本題要求考生模擬堆疊的運作流程，並透過邏輯推論排除不可能的輸出序列。由於必須對多個選項分別驗證操作步驟，且需精確掌握後進先出原則以避免混淆，因此被評定為此難度。
正確答案：④ZXY
④ ZXY:ZXY 是不可能產生的序列。要讓 Z 最先輸出，必須將 X、Y、Z 全部壓入堆疊，此時堆疊由底到頂為 X、Y、Z。彈出 Z 後，堆疊頂端是 Y 而非 X，因此下一個輸出必然是 Y，無法得到 X 在 Y 之前的 ZXY 排列。
錯誤選項解析
- ① XYZ:XYZ 是合法的堆疊輸出序列。依序將 X 壓入後立即彈出得到 X，再將 Y 壓入後立即彈出得到 Y，最後將 Z 壓入後彈出得到 Z，即可產生 XYZ 序列。
- ② YXZ:YXZ 是合法的堆疊輸出序列。先將 X、Y 依序壓入堆疊，彈出 Y 得到第一個輸出，再彈出 X 得到第二個輸出，最後壓入 Z 並彈出即可得到 YXZ。
- ③ YZX:YZX 是合法的堆疊輸出序列。先將 X、Y 壓入堆疊，彈出 Y 後，再將 Z 壓入並彈出得到 Z，最後彈出堆疊底部的 X，即可產生 YZX 序列。
Learning Tip
"堆疊 (Stack) 遵循 LIFO（後進先出） 原則。此類題型的常考陷阱在於判斷給定輸入順序下，哪些輸出排列是堆疊不可達排列 (Stack-inaccessible Permutation)。解題關鍵：當某個元素要輸出時，所有比它更早壓入且尚未彈出的元素，必須按照由頂到底的順序依序彈出，無法跳過中間元素。對於 n 個元素的合法輸出序列數為 卡塔蘭數 (Catalan Number)，公式為 C(n) = (2n)! / ((n+1)! × n!)，三個元素時共有 5 種合法排列。"
學員答題分佈
①XYZ0%
②YXZ0%
③YZX0%
④ZXY0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
將資料1、2、3、4 依序分別經由堆疊(Stack)做排列，則下列何者為不可能之輸出？
一連串的push(推入)與pop(取出)可改變一個序列的順序，例如原始序列為1,2,3，經由push,pop,push,push,pop,pop 操作後，將變成1,3,2 。若原始序列為1,2,3,4,5,6，經由相關操作後，可能產生的序列有那些？
若有一堆疊(Stack)的資料結構，PUSH(X)代表將暫存器X 的內容放入堆疊當中，POP(X)代表從堆疊取出一個數字放入暫存器X 中。假設暫存器A、B、C、D 的內容分別為20、30、40、50，則依序執行PUSH(A)、PUSH(B)、PUSH(C)、POP(A)、PUSH(D)、PUSH(B)、POP(A)、POP(B)後，暫存器B 中的內容為何？
將資料1、2、3、4 依序分別經由佇列(Queue)做排列，則下列敘述何者是正確的？
對堆疊(Stack)的敘述，下列何者為錯誤？