Q187.
下列為含有五個運算元之運算式，此運算式是以後序追蹤(Postorder Traversal)方式表示，其中"*"表示乘法運算，這些後序追蹤所對應的運算樹(Expression Tree)，其高度何者是最高？
電腦軟體設計共同科目 · 乙級 · Q187
難易度分析
3 / 5
本題要求分析後序運算式轉換為運算樹後的結構特徵。考生必須能夠在心算或草擬過程中，將四組不同的運算順序還原為樹狀結構，並區分平衡樹與退化樹的高度差異。由於需要對多個選項進行對比分析且涉及數據結構的空間推演，具有一定挑戰性。
正確答案：③1 2 * 3 * 4 * 5 *
③ 1 2 * 3 * 4 * 5 *:此後序運算式 `1 2 * 3 * 4 * 5 *` 會形成完全左傾斜樹（或右傾斜），每次運算結果都與下一個運算元繼續運算，導致樹高達到最大值 5（等於運算元數量）。
錯誤選項解析
- ① 1 2 3 * * 4 5 * *:此後序運算式對應的運算樹結構較為平衡，乘法運算分散於不同層級，樹高約為 4，並非最高。
- ② 1 2 * 3 4 * 5 * *:此運算式的運算元分組使得樹結構呈現部分傾斜，但仍有分支合併的情況，樹高約為 4，未達最高。
- ④ 1 2 * 3 4 * * 5 *:此運算式存在子運算式合併的情況（3 4 * 與 1 2 * 的結果先相乘），使樹結構產生分支而非單純傾斜，樹高約為 4，非最高。
Learning Tip
"後序追蹤（Postorder Traversal）轉換為運算樹（Expression Tree）時，樹高取決於運算式的傾斜程度。當運算結果持續與下一個運算元進行運算（如選項3的連鎖乘法），會形成退化樹（Degenerate Tree），樹高等於運算元數量。若運算式具有平衡的子運算式分組，則樹高會接近 log₂(n)。此類題型常考平衡樹與傾斜樹的高度差異，需熟練由後序運算式重建運算樹的技巧。"
學員答題分佈
①1 2 3 * * 4 5 * *0%
②1 2 * 3 4 * 5 * *0%
③1 2 * 3 * 4 * 5 *0%
④1 2 * 3 4 * * 5 *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)才能執行無誤？