計概16-08前序－公職試題

【選擇題】

【B】01.最小堆積樹(Min Heap)如圖所示，執行節點刪除後，此最小堆積樹前序走訪(Preorder Traversal)的結果為何？ (A)6 13 16 18 9 (B)6 13 18 16 9 (C)9 6 13 16 18 (D)18 6 13 16 9。[109地方四等資處]

 

【D】02.對一個有九個節點的二元搜尋樹(Binary Search Tree)作前序訪問(Preorder Traversal)，並依序輸出訪問節點的數值，其結果如下(次序由左至右)：12, 9, 7, 8, 20, 15, 13, 16, 22。在此樹中兩個節點之間的路徑(Path)最多含有多少個邊(Edge)？ (A)3 (B)4 (C)5 (D)6。[109身心四等]

8到13或16最多含有6個邊

        12

     /      \

   9         20

  /         /    \

7         15    22

  \      /    \

   8   13    16

 

【B】03.一個前序表示法算式：+ 5 * 6 7其計算結果為何？ (A)37 (B)47 (C)72 (D)210。[110身心五等]

5 + 6 * 7 = 5 + 42 = 47

 

【A】04.請問下列二元樹其前序走訪(Pre-order)何者正確？ (A)BQAVNRSMP (B)BQVNSARMP (C)AQVNBRMSP (D)ANVQMPSRB。[110國安五等資處]


前序：BQAVNRSMP

中序：AQVNBRMSP

後序：ANVQMPSRB

層序：BQVNSARMP

 

【C】05.圖示為一個二元表示樹(expression tree)，下列何者為其前序(Preorder)輸出？+*/–ABCDE (A)+/BC*-DEA (B)+*-DEABC (C)+*-DEA/BC (D)+*A-DE/BC。[110鐵路員級]


 

【D】06.將節點16、3、10、35、6、17、23、4，依順序加到一個沒有資料的二元搜尋樹中，這棵樹的前序追蹤(preorder traversal)的輸出是什麼？ (A)3、4、6、10、16、17、23、35 (B)4、16、10、3、23、17、35、6 (C)4、6、10、3、23、17、35、16 (D)16、3、10、6、4、35、17、23。[111身心五等]

    16

  /    \

3       35

  \      /

   10  17

   /     \

  6     23

 /

4

前序追蹤：16、3、10、6、4、35、17、23

 

【D】07.(A×B+C)+D×E之前序式表示法為何？ (A)+×+AB×CDE (B)×++×ABCDE (C)×+×AB+CDE (D)++×ABC×DE。[111身心四等]

(A×B+C)+D×E → +×ABC+D×E → ++×ABC×DE

 

【D】08.二元搜尋樹是建立在樹節點鍵值的大小上。左子樹的所有鍵值均小於樹根的鍵值，右子樹所有鍵值均大於樹根的鍵值。而高度平衡二元搜尋樹則又定義某一個節點右子樹跟左子樹的高度，高度差的絕對值要小於等於1，否則需要做調整，但調整的方法，最後必須維持二元搜尋樹的特質。在建立二元搜尋樹時，如果鍵值分別是50、40、60、30、45。此時若再加入20，此二元搜尋樹的高度平衡原則就會被破壞。請問根據高度平衡的原則去調整後，最後的二元搜尋樹的前序走訪的結果為何？ (A)20 30 40 50 45 60 (B)40 30 20 45 50 60 (C)50 40 30 60 20 45 (D)40 30 20 50 45 60。[112初考資處] 

 

【A】09.下列的運算式是以前序法(prefix)表示：+ 4 * 9 + 3 2，請問運算的結果為何？ (A)49 (B)41 (C)28 (D)50。[112國安五等]

+ 4 * 9 + 3 2

→ + 4 * 9 (3 + 2) → + 4 * 9 5

→ + 4 (9 * 5) → + 4 45

→ 4 + 45 → 49


【C】10.有一棵二元樹之前序(Prefix)走訪結果為B、A、D、C、E、H、F、G，若此二元樹根節點之右子樹的樹根為E，則此二元樹根節點之左子樹的節點個數為何？ (A)1 (B)2 (C)3 (D)4。[113地方四等電子]

前序走訪順序：根節點 → 左子樹 → 右子樹，根節點在前面，結果為：根左右。

根：B

左子樹根：A

右子樹根：E

左子樹節點：ADC

 

【A】11.一株二元樹如下圖，採用前序(preorder)追蹤方式的拜訪順序為 (A)400, 300, 250, 350, 500, 550, 525, 575 (B)250, 300, 350, 400, 500, 525, 550, 575 (C)250, 350, 300, 525, 575, 550, 500, 400 (D)250, 350, 300, 500, 525, 575, 550, 400。[113身心五等]

 

【A】12.給定前置式(Prefix)數學式/*+ab-cd-e，若a=5,b=4,c=3,d=2,e=1，則運算結果應為多少？ (A)-9 (B)0.6 (C)9 (D)-0.6。[110普考電子]

(a+b)*(c-d)/-e=(5+4)*(3-2)/-1=-9

 

【A】13.此運算式樹(Expression tree)前置式(Prefix)數學式，應為下列何者？ (A)+a/*bc+de (B)a+b*c/(d+e) (C)abc*de+/+ (D)a+/*bc+de。[111鐵路員級]

前置式之順序：根節點、左子節點、右子節點。數學式為+a/*bc+de

 



留言

張貼留言

這個網誌中的熱門文章

計概16-09後序－公職試題

圖片
【選擇題】 【 C 】 01. 以後序 (postorder) 方式走訪下圖中的運算樹，且輸出走訪到的節點內容，下列何者為輸出的字串？ (A)*A+BC (B)A*B+C (C)ABC+* (D)ABC*+ 。 [109 地方四等電子 ] 後序走訪順序：左子樹 → 右子樹 → 根節點。   【 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...
閱讀完整內容

計概16-06樹－公職試題

圖片
【選擇題】 【 C 】 01. 下列何種樹狀資料結構，不保證為平衡樹 (Balanced tree) ？ (A) 完整二元樹 (Complete binary tree) (B) 完滿二元樹 (Full binary tree) (C) 二元搜尋樹 (Binary search tree) (D) 最小堆積 (Min heap) 。 [113 地方四等電子 ] 平衡樹的左右子樹高度差不超過 1 。 1 、 2 、 3 、 4 組成的二元搜尋樹，會往右傾斜，左右子樹高度差會超過 1 。   【 B 】 02. 若以廣度優先搜尋 (Breadth-first Search) 走訪下圖 ( 從節點 1 開始 ) ，各節點的走訪順序應為何？ ( 若同時有多個選擇，請優先挑選數字較大的節點 ) (A)123456 (B)143265 (C)146523 (D)146532 。 [113 地方四等電子 ] 廣度優先搜尋 (BFS) ：從根節點開始，沿著樹的寬度搜尋樹的所有節點，直到找到結果為止。   【 C 】 03. 在一個高度為 7 層的二元樹結構中，其總節點數最多為 (A)256 (B)128 (C)127 (D)255 。 [113 身心五等 ] 2 ^ 7 - 1 = 127 個節點   【 C 】 04. 關於 AVL 樹的敘述，下列何者錯誤？ (A)AVL 樹是一種二元搜尋樹 (B) 在 AVL 樹中，任一節點的兩棵子樹的最大高度差為 1 (C) 在一有 n 個節點的 AVL 樹中插入或刪除一個節點資料，平均複雜度為 O(1) (D)AVL 樹可用來進行排序。 [113 身心四等電子 ] AVL 樹為確保搜尋效率，平均情況下，尋找、插入和刪除操作的時間複雜度都是 O(log n) 。   【 C 】 05. 若執行下列 C 語言程式， #include<stdio.h> #include<stdlib.h> struct node {   char data;   struct node *left;   struct node *right; }; void main(){...
閱讀完整內容

計概16-09後序－統測試題

圖片
【二技試題】 【 C 】 01. 中序式 (Infix form) 表示的運算式 B-C+D*E/(F-G) ， 如果轉換成為後序式 (Postfix form) 應為 (A)+-BC/*DE-FG (B)BCDEFG+-*/- (C)BC-DE*FG-/+ (D)GF-E/D*C+B- 。 [91 護理 ]   【 D 】 02. 某個二元樹 (binary tree) 的前序式 (preorder) 為 ABDFGEC ，中序式 (inorder) 為 FDGBAEC ，則其後序式 (postorder) 為何？ (A)FDGBECA (B)FGDBECA (C)FDGBCEA (D)FGDBCEA 。 [92 管理 ]   【 A 】 03. 假設 a = 5, b = 4, c = 3, d = 2 ，則依後序 (postfix) 運算式 ab * cd + / 之計算值為何？ (A)4 (B)11.5 (C)0.25 (D)10.5 。 [92 護理 ]   【 C 】 04. 後序 (postfix) 運算式 6,3,/,3,-,5,2,*,+ 之計算結果為何？ (A)3 (B)6 (C)9 (D)11 。 [95 護理 ]   【 A 】 05. 有一個中序 (infix) 表示式為 (a/(b-c+d)) × e-a × c ，則此式之後序 (postfix) 表示式為何？ (A)abc-d+/e×ac×- (B)ab/c-de×+ac×- (C)abcdeac-+/-×× (D)abcd-+/ea-c×× 。 [96 電機 ]   【 D 】 06. 假設 W = 4, X = 2, Y = 5, Z = 3 ，後序 (posrfix) 運算式為 WX/YZ-+X* 的值為何？ (A)6 (B)7 (C)12 (D)8 。 [97 管理 ]   【 D 】 07. 若有一個中序 (infix) 式為 ((a+b)+c × (p-q))/(r-s/t) ，其後序式應為下列何者？ (A)abc+-p+/q×rst/- (B)ab/c-p+q+rst×-/ (C)ab+cpqrst-+/-×/ (D)ab+cpq-×+rst/-...
閱讀完整內容