計概16-07中序－公職試題

【選擇題】

【B】01.若一個二元樹(binary tree)有n個節點，使用中序走訪(inorder traversal)的時間複雜度，下列何者正確？ (A)θ(log n) (B)θ(n) (C)θ(n log n) (D)θ(n²)。[110關務四等]

時間複雜度為O(n)

 

【B】02.請問下列二元樹的中序走訪(inorder traversal)何者正確？ (A)9,5,3,1,4,8,6,20,12,10,11,30,21,31 (B)1,3,4,5,6,8,9,10,11,12,20,21,30,31 (C)1,4,3,6,8,5,11,10,12,21,31,30,20,9 (D)9,5,20,3,8,12,30,1,4,6,10,21,31,11。[111身心五等]

中序走訪，依序先走訪左子節點、根節點、右子節點。

 

【C】03.將後序表示式(postfix expression)abc*+de-*進行轉換，下列敘述何者正確？ (A)中序表示式(infix expression)為a+b*c*d-e (B)中序表示式(infix expression)為(a+b)*c*(d-e) (C)中序表示式(infix expression)為(a+b*c)*(d-e) (D)中序表示式(infix expression)為a+b*(c*d-e)。[111初考資處]

abc*+de-* → 中序表示式為(a+b*c)*(d-e)

 

【D】04.若一個最大堆積樹(Max Heap)如圖所示，加入一個新節點9後，則此最大堆積樹中序走訪(Inorder Traversal)的結果為何？ (A)4 6 2 7 8 9 (B)4 6 2 7 9 8 (C)4 6 2 8 9 7 (D)4 6 2 9 7 8。[112地方四等資處]

 

【D】05.有一個二元樹，它的後序走訪(postorder traversal)的結果是CBEFDA，那麼它的中序走訪的結果，不可能是下列那一個？ (A)BCAEDF (B)ACEBFD (C)CBEFDA (D)BACDCF。[112國安五等]

(D)節點C重複，不可能。

 

【A】06.下列是scheme的function：

(define(cube x) (*(*x x) x))

(define(double x) (* 2 x))

(define(five x) (* 5 x))

(define(poly x) (+(-(double(cube x))(five x))1))

那麼執行(poly 2)的結果是多少？ (A)7 (B)12 (C)-3 (D)55。[112國安五等]

(cube x) = x * x * x = x ^ 3

(double x) = 2 * x = 2x

(five x) = 5 * x = 5x

(poly x) = +(-(double(cube x))(five x))1 = ((double(cube x)) - (five x)) + 1 = (2 * (x ^ 3) - 5x) + 1

(poly 2) = (2 * (2 ^ 3) - 5 * 2) + 1 = 7