某程式產出一個資料序列，依A、B、C 的順序（A 最先）輸入到一個空的堆疊（Stack），藉由推入（Push）、彈出（Pop）的動作以改變原本的資料順序，總共有…

題目

某程式產出一個資料序列，依A、B、C 的順序（A 最先）輸入到一個空的堆疊（Stack），藉由推入（Push）、彈出（Pop）的動作以改變原本的資料順序，總共有幾種可能的輸出順序？ A. 6 種 B. 5 種 C. 4 種 D. 3 種

官方答案

• 答案：B. 5 種

解析

A、B、C 依序 Push，過程中可隨時 Pop，屬於典型的堆疊排列問題。n 個元素可能的輸出順序數為卡塔蘭數（Catalan number）C(n)=C(2n,n)/(n+1)。以 n=3 代入：C(6,3)/4=20/4=5，故共有 5 種。實際列出為 ABC、ACB、BAC、BCA、CBA；其中 CAB 無法達成，因為要讓 C 最先輸出，必須先 Push A、B、C 再 Pop C，此時堆疊頂端為 B，下一個只能輸出 B，不可能輸出 A。因此答案為 5 種。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。