Q189.
下列為含有六個運算元之運算式，此運算式是以後序追蹤(Postorder Traversal)方式表示，其中"*"表示乘法運算，這些後序追蹤所對應的運算樹(Expression Tree)，其高度何者是最高？
電腦軟體設計共同科目 · 乙級 · Q189
難易度分析
4 / 5
本題要求將多個後序表達式還原為運算樹並比較高度，考生必須能精確區分平衡結構與鏈狀結構的差異，且需對所有選項逐一進行複雜的邏輯推演，對運算樹的建構過程要求精準度高。
正確答案：②1 2 3 * * 4 * 5 * 6 *
② 1 2 3 * * 4 * 5 * 6 *:此後序運算式會形成嚴重左傾的鏈狀運算樹，每次運算都將前次結果作為左運算元繼續堆疊，形成 ((((1*(2*3))*4)*5)*6) 的結構，樹高達 6，為所有選項中最高。
錯誤選項解析
- ① 1 2 * 3 4 * * 5 6 * *:此後序運算式構建的運算樹為左右平衡結構，根節點左子樹為 ((1*2)*(3*4))，右子樹為 (5*6)，樹高為 4，並非最高。
- ③ 1 2 3 * * 4 5 * * 6 *:此運算式前半部形成左傾子樹 (1*(2*3))，但後半部 (4*5) 與其合併後再與 6 運算，樹高為 5，低於選項 2 的鏈狀結構。
- ④ 1 2 * 3 4 5 * * * 6 *:此運算式先構建 (1*2) 與 (3*(4*5)) 兩個子樹後合併，再與 6 運算，整體樹高為 5，同樣未達選項 2 的高度。
Learning Tip
"後序追蹤(Postorder Traversal) 轉換為運算樹(Expression Tree) 時，樹高取決於運算元的排列方式。當運算式呈現「連續運算元後接多個運算子」的形態（如 1 2 3 * * 4 * 5 * 6 *），會形成單側傾斜的鏈狀樹，樹高最大；若運算式能均勻分配左右子樹的運算元數量，則樹高較小。此類題型常考陷阱在於誤判運算子的結合順序，解題關鍵是依照堆疊(Stack) 原理逐步還原運算樹的建構過程。"
學員答題分佈
①1 2 * 3 4 * * 5 6 * *0%
②1 2 3 * * 4 * 5 * 6 *0%
③1 2 3 * * 4 5 * * 6 *0%
④1 2 * 3 4 5 * * * 6 *0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
下列為含有五個運算元之運算式，此運算式是以後序追蹤(Postorder Traversal)方式表示，其中"*"表示乘法運算，這些後序追蹤所對應的運算樹(Expression Tree)，其高度何者是最高？
下列為含有五個運算元之運算式，此運算式是以前序追蹤(Preorder Traversal)方式表示，其中"*"表示乘法運算，這些前序追蹤所對應的運算樹(Expression Tree)，其高度何者是最高？
假設有一個infix 運算式(A – B) * (C + D)，我們建造其所對應的運算樹(Expression Tree)，下列那些正確？
假設有一個Postfix 運算式A B + C / C B + D * +，而其值為A=3，B=6，C=3，D=2 。該運算式執行之後，十位數為m，個位數為n，下列那些正確？
將A×(B-C/(D+E))轉成後序式後，最少需要多大容量的堆疊(Stack)才能執行無誤？