調查局三等申論題
109年
[電子科學組] 計算機概論
第 一 題
📖 題組：
本題有關二元樹與算術運算式。
本題有關二元樹與算術運算式。
📝 此題為申論題，共 2 小題
小題 (一)
某一個算術運算式（arithmetic expression）利用二元樹（binary tree）做後序拜訪（postorder traversal），轉換成後序式（postfix）為：A B C / D – E * + F G / –，其中 A、B、C、D、E、F、G 代表運算元（operand），+（加）、–（減）、*（乘）、/（除）代表運算子（operator）。如果該算術運算式帶入 A=5, B=6, C=2, D=3, E=2, F=9, G=3，則計算結果的值是多少？（15分）
思路引導 VIP
看到「後序式（Postfix）的數值計算」，應立刻聯想到使用「堆疊（Stack）」資料結構來解題。解題核心為：由左至右讀取字元，遇到運算元（數字）即推入堆疊（Push），遇到運算子則從堆疊彈出（Pop）兩個數值進行計算（注意先彈出的是右運算元，後彈出的是左運算元），再將結果推回堆疊，最後留在堆疊內的數值即為解答。
小題 (二)
已知某二元樹有3個節點，且該二元樹經後序拜訪的輸出結果依序是 C、B、A。請列出所有滿足上述條件的二元樹。（10分）
思路引導 VIP
看到此題，應先聯想後序走訪（Postorder）的順序為「左子樹、右子樹、根節點」，因此輸出序列最後的 A 必定是整棵樹的根節點。接著利用卡塔蘭數（Catalan number）算出 3 個節點的二元樹共有 5 種形狀，依序將 C、B、A 填入並驗證，即可窮舉所有答案。