計概16-09後序－公職試題
後序走訪順序：左子樹 → 右子樹 → 根節點。
【D】02.某二元樹有3個節點，經後序走訪(postorder traversal)結果輸出C、B、A，該二元樹有幾種可能？ (A)3 (B)9 (C)7 (D)5。[109地方四等電子]
【D】03.將中序運算式(Infix Expression)1(23/4)*5+-轉換為後序運算式(Postfix Expression)的結果為何？ (A)12+34/5*-
(B)12+345*/- (C)123-4/5*+ (D)1234/-5*+。[109關務四等]
1+(2-3/4)*5 → 1+((2-(3/4))*5) → 1234/-5*+
由右往左，將運算子取代最近的右括號
【C】04.某一個二元樹的前序(pre-order)順序為ABCDEFGHI，中序(in-order)順序為BCAEDGHFI，則其後序(post-order)順序為何？ (A)ABDCEFGIH
(B)BCADGFIE (C)CBEHGIFDA (D)DHGFEICBA。[109鐵路員級]
前序找最前，中序分左右，後序找最後。
前序：ABCDEFGHI，最前為(A)
中序：BCAEDGHFI，以(A)為中，分成左(BC)，右(EDGHFI)
後序的順序為"左右中"，A放在最後，則左(BC)右(EDGHFI)中(A)，選(C)。
【B】05.如果某一個二元樹的前序與中序表示法為：c, a, b, d, g, e, f與b, a, g, d, c, e, f，則其後序表示法為何？ (A)b, d, g, a, f, e, c
(B)b, g, d, a, f, e, c (C)b, g, d, a, e, f, c (D)c, a, b, d, g, e, f。[110身心五等]
c
/ \
a e
/ \ \
b d f
/
g
【C】06.若輸入一串數字2，9，3，6，10，4，8以建立二元搜尋樹(Binary Search Tree)，則此二元搜尋樹後序走訪(Postorder Traversal)的結果為何？ (A)2 4 3 8 10 9 6 (B)3
4 8 6 10 9 2 (C)4 8 6 3 10 9 2 (D)6 3 9 2 4 8 10。[110身心四等]
2
\
9
/ \
3 10
\
6
/ \
4 8
【A】07.有一個二元樹，A~I為其節點，其先序(preorder)為ABDHIECFG，中序(inorder)為HDIBEAFCG，求其後序(postorder)為何？ (A)HIDEBFGCA (B)HIDFGCEBA (C)GFCEIHDBA (D)IDHEBAGFC。[110國安五等資處]
先序：ABDHIECFG
中序：HDIBEAFCG
後序：HIDEBFGCA
層序：ABCDEFGHI
【D】08.已知5763+-*是某一個算術運算式(Arithmetic expression)的後序表示式(Postfix expression)，則該運算式計算後的值(Value)為多少？ (A)36 (B)-18
(C)-6 (D)-10。[111普考電子]
5763+-* → 5*(763+-) → 5*(7-63+) → 5*(7-(6+3)) → 5*(7-9) → 5*(-2) → -10
【A】09.下列何者為一個n個點二元搜尋樹(Binary search tree)，使用後序走訪(Post-order traversal)在最差情況下(Worst case)之時間複雜度？ (A)O(n) (B)O(n log n) (C)O(n2)
(D)O(log n)。[111鐵路員級]
最差情況下，每個節點均走訪一次，時間複雜度為O(n)。
【D】10.將運算式子(a+b)*d+e/(f+a*d)+c轉換為後序(Postfix)運算式子 (A)abdefadc+*+/+*+ (B)ab+d*+e/f+a*d+c
(C)cefad*+/+ab+d*+ (D)ab+d*efad*+/+c+。[111鐵路員級]
(a+b)*d+e/(f+a*d)+c
→ ((a+b)*d)+(e/(f+(a*d)))+c 先乘除
→ (((a+b)*d)+(e/(f+(a*d))))+c 後加減
→ ((((a+b)*d)+(e/(f+(a*d))))+c)
→
a+b)*d)+e/f+a*d))))+c) 去左括號
→ ab+d*efad*+/+c+ 右括號取代為左邊最接近的運算子(由最內層開始)
【C】11.關於二元樹狀結構的後序走訪(traversal)，所產生的後置運算式，下列何者正確？ (A)+ × a + b c
d (B)a × (b + c) + d (C)a b c + × d + (D)a b c × + + d。[112身心五等]
後序(Postorder)走訪順序：左子樹 → 右子樹 → 根節點，根節點在後面，結果為：a b c + × d +
【B】12.若a = 4, b = 3, c = 2, d =
5, e = 10, f = 2, g = 3, h = 2，則後置式(Postfix)數學式abcd*ef/+gh*-+-的運算結果為何？ (A)-290 (B)-8 (C)10
(D)144。[109地方四等電子]
abcd*ef/+gh*-+- →
a-(b+(c*d)+(e/f)-(g*h))
4 - (3 + (2 * 5) + (10 / 2) - (3
* 2)) = 4 - (3 + 10 + 5 - 6) = 4 - 12 = -8
【D】13.將以前置式(Prefix)呈現的數學運算式+*+P^QRS^TU轉換成後置式(Postfix)，結果應為下列何者？ (A)PQ+R^S*T+U^
(B)P+Q^R*S+T^U (C)(P+Q^R)*S+T^U (D)PQR^+S*TU^+。[109普考電子]
+*+P^QRS^TU → {+[*(+P(^QR))S](^TU)}
→ {[(P(QR^)+)S*](TU^)+}
→ PQR^+S*TU^+
前置式第一個一定是根節點，後置式最後一個一定是根節點。
【A】14.若某算術運算式的前置(prefix)表示法為為×+ a b- c d，則它的後置(postfix)表示法是 (A)ab+ cd-× (B)ab cd+ -
× (C)ab+ cd×- (D)ab +- cd×。[109普考電子]
×+ab-cd → [×(+ab)(-cd)] → ab+cd-×
【A】15.若i=5, j=6，且k=8，下列那個後置式(Postfix)數學式的運算結果，能得到最大的數值？ (A)ij+k* (B)ijk*+
(C)ij*k+ (D)ijk+*。[110地方四等電子]
(A)(5+6)*8=88。(B)5+6*8=53。(C)5*6+8=38。(D)5*(6+8)=70
【D】16.下列的後置算術運算式(postfix
expression)822*-75*+所計算出來的值為何？ (A)24 (B)35 (C)40 (D)39。[110國安五等]
(8 - 2 * 2) + 7 * 5 = 4 + 35 = 39
【D】17.若a=6, b=2, c=3, d=2, e=3，後置式(Postfix)數學式ab/cde*^+的運算結果應為何？ (A)27 (B)30 (C)219
(D)732。[111普考電子]
ab/cde*^+ → 62/323*^+ → (6/2)323*^+ → (6/2)+(323*^) → (6/2)+(3^23*) → (6/2)+(3^(2*3)) → 3+3^6 → 3+729 → 732
留言
張貼留言