計概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


【A】10.給定前置式(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】11.此運算式樹(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)c, a, b,
閱讀完整內容

計概16-06樹－公職試題

圖片
【選擇題】 【 B 】 01. 關於一個有 n 個節點的紅黑樹 (red-black tree) ，下列敘述何者錯誤？ (A) 根節點 (root) 是黑色 (B) 如果一個節點是黑色，它的兩個子節點都會是紅色 (C) 葉節點 (leaf) 是黑色 (D) 從根節點到葉節點的每個路徑中，黑色節點的數量必須一樣。 [109 地方四等資處 ] 紅黑樹的特性： 1. 根節點是黑色。 2. 葉節點是黑色。 3. 從根節點到葉節點的每個路徑中，黑色節點的數量必須一樣。 4. 每個節點，可紅可黑。 5. 節點是紅色，子節點必為黑色。節點是黑色，子節點可紅可黑。   【 A 】 02. 若從數列 [1, 3, 5, 7] 中，依序取出其中的數字來建立二元搜尋樹 (binary search tree) ，則該樹為下列何者？ [109 地方四等電子] 二元搜尋樹 (binary search tree) ：小      中      大 第 1 個數字 1 當樹根。第 2 個數字 3 ， 1 ＜ 3 ， 3 放在 1 的右邊。 第 3 個數字 5 ， 3 ＜ 5 ， 5 放在 3 的右邊。第 4 個數字 7 ， 5 ＜ 7 ， 7 放在 5 的右邊。   【 B 】 03. 關於下圖二元搜尋樹 (binary search tree ， BST) ，下列何者正確？ (A) 若對 BST 做中序瀏覽 (inorder traversal) 可以產生一個依降冪排列的有序串列 (B) 若對 BST 做廣度優先瀏覽 (breadth first traversal) 產生的串列並沒有一定的秩序 (C) 若對 BST 做後序瀏覽 (postorder traversal) 可以產生一個依昇冪排列的有序串列 (D) 若對 BST 做前序瀏覽 (preorder traversal) 可以產生一個依昇冪排列的有序串列。 [109 身心五 等 ] 對 BST 做 中序瀏覽 產生升 冪排列的有序串列。廣度優先瀏覽產生的串 列並無唯一解。   【 C 】 04. 下列有關高度為 h 、節點數為 n 的二元搜尋樹之敘述，何者錯誤？ (A) 搜尋特定節點所需時間與 h 成正比 (B) 依由小到大之次序輸出所有結點資料
閱讀完整內容

計概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/-/ 。 [98 電機 ]   【 C 】 08.
閱讀完整內容