民國111年 第2梯次 電腦軟體設計(C++)乙級 學科
第33題
下列為含有六個運算元之運算式,此運算式是以後序追蹤(Postorder Traversal)方式表示,其中"*" 表示乘法運算,這些後序追蹤所對應的運算樹(Ex…
題目
下列為含有六個運算元之運算式,此運算式是以後序追蹤(Postorder Traversal)方式表示,其中"*" 表示乘法運算,這些後序追蹤所對應的運算樹(Expression Tree),其高度何者是最高?
- (1) 123 * * 45 * * 6 *
- (2) 12 * 345 * * * 6 *
- (3) 123 * * 4 * 5 * 6 *
- (4) 12 * 34 * * 56 * *
官方答案
(3) 123 * * 4 * 5 * 6 *
解析
後序式可用堆疊建樹：運算元先入堆疊，每讀到一個運算子就彈出兩個子樹結合成新樹。第 3 式依序建成 ((((1*(2*3))*4)*5)*6)，是往左傾斜的鏈狀結構，由根到最深葉節點共經過 6 層，高度為 6。第 1 式為 (1*(2*3))*(4*5) 再乘 6，高度 5；第 2 式為 (1*2)*(3*(4*5)) 再乘 6，高度 5；第 4 式為 (1*2)*(3*4) 再乘 (5*6)，高度 4。故以第 3 式最高。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。