計概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)依由小到大之次序輸出所有結點資料所需時間與n成正比 (C)對任一n筆資料序列進行tree sorting所需最少時間與n的平方值成正比 (D)對任一n筆資料序列進行tree sorting所需最多時間與n的平方值成正比。[109身心四等]

最少時間為O(1)

 

【C】05.在二元搜尋樹(Binary Search Tree)上，最大的值必定 (A)為根節點(root) (B)為葉節點(leaf) (C)有至多一個子節點 (D)有至少一個子節點。[109身心四等]

根節點：沒有父節點的節點。

葉節點：沒有子節點的節點。

二元搜尋樹一個節點最多只有二個子節點。

 

【C】06.4個節點可組成幾個不同之二元樹(distinct binary tree)？ (A)5 (B)9 (C)14 (D)16。[109身心四等]

卡塔蘭數，[(8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) / (4 * 3 * 2 * 1 * 4 * 3 * 2 * 1)] / (4 + 1) = 14

 

【C】07.若一個非空的二元樹(Nonempty Binary Tree)使用n代表節點數量以及h代表高度(Height)，並定義根節點(Root)的高度為0，則有關節點數量與高度，下列敘述何者錯誤？ (A)節點數量n最小值為h + 1 (B)節點數量n最大值為2^{h + 1} - 1 (C)高度h最小值為log₂(n + 1) (D)高度h最大值為n - 1。[109普考資處]

節點高度 = 1，高度h最小值為log₂(n + 1)

節點高度 = 0，高度h最小值為[log₂(n + 1)] - 1

 

【C】08.假設有一個二元搜尋樹(binary search tree)，其節點儲存的數值介於1至100之間，下列何者是不可能出現的搜尋過程？ (A)33, 41, 55, 62, 77, 64 (B)5, 12, 21, 70, 33, 23 (C)50, 32, 40, 35, 37, 41 (D)80, 20, 75, 66, 32, 30。[109普考資處]

二元搜尋樹：左子樹的值一定比節點小；右子樹的值一定比節點大。

(C)最後的值41比40大。

 

【B】09.下列關於資料結構的敘述何者錯誤？ (A)就動態增加新的元素而言，以樹(tree)作為資料結構較以陣列(array)作為資料結構更為適合 (B)就儲存相同數目資料之空間需求而言，以樹作為資料結構所使用的空間較以陣列作為資料結構所使用的空間為少 (C)就搜尋資料結構裡的特定元素而言，樹所需的搜尋時間可以為O(log n) (D)就搜尋資料結構裡的特定元素而言，未排序之陣列所需的搜尋時間為O(n)。[109普考電子]

(A)tree使用linked list直接修改，新增刪除方便。array新增刪除可能需要移動array的資料，如刪除第1筆資料，須將2~n筆資料往前移動。(B)儲存相同數目資料，tree和array使用的空間相同。(C)二分搜尋法的平均時間複雜度為O(log n)。(D)未排序之陣列，搜尋時間最久為O(n)，最後一個才找到。

 

【D】10.在下列的graph中，那個節點不是articulation point？ (A)b (B)i (C)e (D)a。[109普考電子]

關節點(articulation point)：從圖中移除這個節點會形成無法連通的圖。

 

【B】11.對一個有十二個節點的二元搜尋樹(Binary Search Tree)作後序訪問(Postorder Traversal)，並依序輸出訪問節點的數值，其結果如下(次序由左至右)：3, 4, 6, 5, 8, 15, 19, 18, 16, 12, 24, 20。在此樹中有多少個節點其左子節點(Left Child)及右子節點(Right Child)皆有數值？ (A)3 (B)4 (C)5 (D)6。[109普考電子]

      20

     /    \

    12    24

   /   \

  8    16

  |    /   \

  5  15   18

 /  \       |

4   6     19

|

3

 

【A】12.下圖中的最小生成樹(Minimum Spanning Tree)其邊的總長為何？ (A)25 (B)26 (C)27 (D)28。[109普考電子]

最小生成樹：最小權重生成樹的簡稱，不形成循環，連接最小權重的連通圖。

3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 = 25

 

【A】13.若一個二元樹(Binary Tree)中序走訪(Inorder Traversal)結果為BCAEDGHF，前序走訪(Preorder Traversal)結果為ABCDEFGH，則節點F的父節點(Parent)為何？ (A)D (B)E (C)G (D)H。[109關務四等]

   A

 /    \

B     D

 \    /  \

 C  E   F

        /

       G

        \

        H

 

【A】14.關於一個圖的最小生成樹(minimum spanning tree)，下列敍述何者錯誤？ (A)具有唯一的最小生成樹 (B)最小生成樹的邊個數是節點個數減1 (C)最小生成樹是一個連通圖(connected graph) (D)在最小生成樹中的任兩點之間加入一個邊之後會產生一個迴路(cycle)。[109關務四等]

最小生成樹可能會有多個。

 

【B】15.若一個二元搜尋樹(binary search tree)中各節點(node)包含的數字範圍為1到3500，在找尋數字1405的過程中，下列何者不可能是所造訪之節點形成的數字序列？ (A)2, 33, 44, 180, 307, 3100, 1300, 1802, 1500, 1404, 1405 (B)3, 2500, 300, 2650, 1400, 1406, 1405 (C)1401, 1402, 1403, 1404, 1405 (D)1405。[109鐵路員級]

(B)2500下一筆為300，不可能找到比2500大的值，再下一筆為2650，矛盾。

 

【A】16.若針對下圖中的樹由樹根(root)開始進行廣度優先搜尋(breadth-first search)，並同時將走訪到的節點標籤輸出，則輸出的字串為下列何者？

    A

   /  \

  B   C

 /  \

D   E (A)ABCDE (B)ABDEC (C)DEBCA (D)DEBAC。[109鐵路員級]

廣度優先搜尋是從根節點開始，沿樹的寬度走訪樹的節點。如果所有節點都被存取，才中止搜尋。

 

【B】17.下圖中可產生多少種不同的生成樹(spanning tree)？ (A)35 (B)40 (C)45 (D)50。[109鐵路員級]

8*1*5=40種

 

【D】18.針對一個具有n個節點的二元搜尋樹(binary search tree)，下列敍述何者錯誤？ (A)由根節點(root)開始，以中序(inorder)方式走訪此二元搜尋樹的時間複雜度為θ(n) (B)在最差狀況下搜尋一個數值的時間複雜度為θ(n) (C)在最差狀況下新增一個數值的時間複雜度為θ(n) (D)在最佳狀況下刪除一個數值的時間複雜度為θ(n)。[110地方四等資處]

(D)最佳狀況的時間複雜度為θ(logN)

 

【C】19.假設二元樹(binary tree)中節點的深度(depth)定義如下：

1.根節點(root)的深度為0

2.如果節點的深度是i，則其子節點的深度是i+1

二元樹的高度(height)定義為樹中所有節點的深度中之最大值

完滿二元樹(full binary tree)中的節點則需滿足以下兩個條件：

1.所有葉節點(leaf nodes)的深度相同

2.非葉節點的分支度(degree)為2

若完滿二元樹的高度為15，則其具有的節點數量為何？ (A)32767 (B)32768 (C)65535 (D)65536。[110地方四等資處]

節點數量=根節點+子節點+葉節點=2⁰+(2¹+2²+…+2¹⁴)+2¹⁵=2¹⁶-1=65536-1=65535

 

【D】20.下列圖示中，左圖是一般樹而右圖是左子右兄弟樹(Left child-right sibling)的資料結構舉例。若此兩種資料結構中所有父子之間的連結和兄弟之間的連結均以雙向指標來實作，下列敘述何者錯誤？

(A)在一般樹的資料結構中，若使用固定個數的欄位儲存指標，則容易造成空間的浪費 (B)在計算節點與根節點(Root)的距離時，使用左子右兄弟樹不會比使用一般樹走訪(Traverse)更少的指標 (C)用左子右兄弟樹的資料結構來確認兩節點之間的父子關係在最差情況下需要檢查超過一個以上的指標 (D)用左子右兄弟樹的資料結構來確認兩節點之間的父子關係較一般樹的資料結構更有效率。[110地方四等電子]

需要確認一個以上的指標，效率較差。

 

【A】21.下列何者不是二元搜尋樹(Binary search tree)？[110地方四等電子]

二元搜尋樹：左子樹小於節點，右子樹大於節點。

(A)右子樹5小於節點8。

 

【B】22.一個二元樹(binary tree)中有14個節點(nodes)，若其分支度(degree)為1的節點共有5個，則此二元樹(binary tree)的樹葉(leaf)節點個數為何？ (A)4 (B)5 (C)7 (D)9。[110初考資處]

n1 = 5

n0 + n1 + n2 = 14

n0 + n2 = 9

n0 - n2 = 1

解方程式：n0 = 5，n2 = 4

 

【C】23.下列依據由左至右順序所建造的二元搜尋樹(Binary Search Tree)中，那一個最為平衡(balanced)？ (A)7, 24, 29, 33, 46, 52, 84 (B)84, 52, 46, 33, 29, 24, 7 (C)33, 24, 52, 7, 29, 46, 84 (D)46, 52, 84, 33, 29, 24, 7。[110國安五等]

依據順序建立節點，小的放左邊，大的放右邊。

 

【B】24.關於Kruskal最小展開樹(minimum spanning tree)演算法，下列敘述何者錯誤？ (A)屬於貪心演算法(greedy algorithm) (B)若圖中存在相同權值的邊，則無法找出最小展開樹 (C)必須先將圖中所有的邊依權值從小到大排序 (D)針對同一個圖，Kruskal演算法和Prim演算法找出的最小展開樹有可能不同。[110普考資處]

當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。

 

【D】25.某棵三元樹(3-ary tree)有6個內部節點(Internal nodes)，且每個內部節點都恰有3個子節點(Children)，則該棵三元樹有多少個葉節點(Leaves)？ (A)10 (B)11 (C)12 (D)13。[110普考電子]

 

【A】26.有一個二元搜尋樹(Binary Search Tree)，每個節點的鍵值都不同，下列敘述何者正確？ (A)最大的鍵值有可能在根節點 (B)樹根節點的鍵值必定大於左右子樹節點的鍵值 (C)是一種平衡樹(Balanced Tree) (D)假設有n個節點，則空間(Space complexity)複雜度平均為O(log n)。[110普考電子]

二元搜尋樹根節點的鍵值，大於左子樹節點的鍵值，但小於右子樹節點的鍵值。

(A)左歪斜樹最大的鍵值有可能在根節點。

 

【A】27.下列何者為n個節點的二元搜尋樹(Binary search tree)最糟搜尋時間複雜度？ (A)O(n) (B)O(log n) (C)O(n^2) (D)O(n log n)。[110鐵路員級]

二元搜尋樹的時間複雜度：最差時間與平均時間O(n)。

 

【D】28.若要將運算式樹(Expression tree)轉換為後置式(Postfix)、前置式(Prefix)和中置式(Infix)等數學式表示法，下列敘述何者錯誤？ (A)若要產生後置式表示法，應該以後序拜訪(Postorder traversal)走訪該樹 (B)若要產生前置式表示法，應該以前序拜訪(Preorder traversal)走訪該樹 (C)若要產生中置式表示法，應該以中序拜訪(Inorder traversal)走訪該樹 (D)上述三種表示法皆需要括號以確保數學式解讀的單一性。[111地方四等電子]

有了Expression tree，就不需要括號，不必再查operator precedence table，可以清楚看出計算的先後順序。

 

【A】29.搜尋一棵二元搜尋樹(Binary search tree)在最佳情況(In best case)要做多少次鍵值(Key)比較？ (A)1 (B)n+1 (C)n–1 (D)(n+1)∕2。[111地方四等電子]

二元搜尋最佳時間O(1)=1次。

 

【A】30.下列何者是平衡樹(Balanced Tree)？ (A)AVL tree (B)Binary Search Tree (C)Huffman Tree (D)Spanning Tree。[111身心四等]

平衡樹：即平衡二元樹(Balanced Binary Tree)，左子樹、右子樹都是平衡的，左右兩子樹的高度差不大於1。常見有紅黑樹、AVL樹、樹堆(Treap)、伸展樹(Splay tree)、紅黑樹(Red-black tree)等。

 

【B】31.從圖中的節點a開始進行廣度優先搜尋(Breadth first search，簡稱BFS)，產生的廣度優先擴張樹(BFS spanning tree)可能為下列何者？[111身心四等]

 (A)(C)(D)均為深度優先搜尋

【C】32.在一個有n個節點(Nodes)的二元樹(Binary tree)中，包含多少個空鏈結(Null links)？ (A)n-1 (B)n (C)n+1 (D)2n-1。[111身心四等]

n個節點的二元樹，包含n+1個空鏈結。

 

【A】33.依順序插入下列整數以建立一棵二元搜尋樹(Binary search tree)：51，16，63，6，21，59，92，4，9，則該二元搜尋樹的樹根(Root)的左子樹(Left subtree)、右子樹(Right subtree)各有多少個節點？ (A)(5, 3) (B)(4, 4) (C)(6, 2) (D)(2, 6)。[111身心四等]

        51

      /     \

    16      63

   /   \    /   \

  6   21  59  92

 /  \

4   9

 

【C】34.使用下列數字序列：20、2、3、4、7、6、9、1、5、8，依序輸入建立一個二元搜尋樹(binary search tree)，下列敘述何者錯誤？ (A)由根節點出發使用前序(preorder)方式走訪此二元搜尋樹，輸出為20,2,1,3,4,7,6,5,9,8 (B)節點1和節點3的父節點相同 (C)節點6位於節點9的左子樹 (D)若最後再新增一個數字10，此二元搜尋樹的高度不變。[111普考資處]

    20

   /

  2

 /  \

1   3

     \

      4

       \

        7

       /  \

      6   9

     /    /

    5   8

 

【D】35.假設一棵二元樹(Binary tree)總共有n個節點，其中每個節點都恰有0個或2個子節點(Children)，該二元樹的內部節點(Internal nodes)有幾個？ (A)(n+1)/2 (B)(n+1)/2-1 (C)n/2-1 (D)(n-1)/2。[111普考電子]

 

【C】36.若樹的高度為葉子(Leaf)節點到根(Root)節點最長路徑之長度加1(即，只有一個節點的樹其高度為1)，則高度為4的二元樹中，最多有幾個節點？ (A)4 (B)8 (C)15 (D)16。[111鐵路員級]

2⁴ – 1 = 15個節點

 

【C】37.下列何者是下圖的展開樹(Spanning Tree)？[111鐵路員級]  

二點數字相加，求最少成本路徑，不能形成迴圈。

(A)(D)有迴圈。(B)原圖③④沒有相連。

 

【C】38.有關二元樹(Binary tree)的節點(Nodes)與邊(Edges)的敘述，下列何者錯誤？ (A)一棵二元樹的總節點數可能是0個 (B)一棵高度(Height)為k的二元樹總節點數最少為k個 (C)一棵二元樹的總節點數與總邊數可能都是奇數(Odd number) (D)一棵二元樹的總節點數可能是1個。[112地方四等電子]

在樹中，邊的條數是節點數減去1。

完全二元樹的總結點數是奇數，則下面的每一行節點數是偶數。

 

【C】39.有關Heap sort演算法，主要是運用何種資料結構來設計？ (A)Queue (B)Stack (C)Tree (D)Linked List。[112地方四等電子]

Heap使用完全二元樹來設計上

 

【A】40.若一棵完滿二元樹(Full Binary Tree)有N個葉節點(Leaf Node)，則該二元樹有多少個非葉節點(Non-leaf Node)？ (A)N-1 (B)N+1 (C)N (D)2N-1。[112身心五等]

完滿二元樹(Full Binary Tree)：高度h，節點個數 = 2^h - 1

高度4，節點個數 = 2⁴ - 1 = 15

葉節點 = N = 8，非葉節點 = N - 1 = 8 - 1 = 7

 

【B】41.二元樹的走訪有前序追蹤(Pre-order)、中序追蹤(In-order)及後序追蹤(Post-order)三種。下列的二元樹，請問若用前序追蹤結果其第三個輸出的節點，中序追蹤結果其第五個輸出的節點，及後序追蹤結果其第八個輸出的節點，各分別是什麼？ (A)(B, E, G) (B)(D, A, C) (C)(H, F, G) (D)(H, E, G)。[112初考資處]

前序：根→左子樹→右子樹→A B D H E C F I G

中序：左子樹→根→右子樹→D H B E A F I C G

後序：左子樹→右子樹→根→H D E B I F G C A

 

【C】42.一個有n個節點的二元樹，共有2n個Link，但實際上有很多鏈結(Link)是浪費掉。為了改善這個問題，就有引線二元樹(Thread Binary Tree)的出現。每一個節點都會有左引線跟右引線分別指到其他合適的節點，並且有額外的欄位來辨識是引線還是正常的指標。若把下圖二元樹的引線畫出來，請問節點I的右引線及節點G的左引線分別指到那個節點？ (A)節點E跟節點F (B)節點B跟節點F (C)節點B跟節點C (D)節點E跟節點C。[112初考資處]

引線二元樹：所有原本為空的右子節點指針改為指向該節點在中序序列中的後繼，所有原本為空的左子節點指針改為指向該節點的中序序列的前驅。

I的右引線：I→D→B

G的左引線：G→C

 

【B】43.擴展樹(Spanning Tree)是圖形理論(Graph Theory)中的一種運用。擴展樹是以最少的邊數來連接圖形中所有的頂點，若圖形中的每一個邊加上一些數值當作權重(Weight)，這樣的權重可以是成本(Cost)或距離(Distance)。雖然一個圖形可能會有許多的擴張樹，但若考慮每個邊上的權重(或成本)，我們可以找到一個最小成本的擴張樹(Minimum Cost Spanning Tree)。以下的圖形，G=(V, E)，V是頂點，V={1, 2, 3, ..., n}，E是連接兩個頂點的邊，邊上的數值代表權重(或成本)。請問下圖中，關於這個圖形的最小成本擴張樹(從頂點1開始出發)，下列何者正確？ (A)頂點4跟頂點7的邊包含在這個最小成本擴張樹中 (B)最小成本擴張樹所有權重總和為50 (C)頂點5跟頂點7的邊包含在這個最小成本擴張樹中 (D)最小成本擴張樹所有權重總和為48。[112初考資處]

最小成本擴張樹①→⑥→⑤→④→③→②→⑦

所有權重總和=1+21+16+2+6+4=50

 

【D】44.最小成本的擴張樹(Minimum Cost Spanning Tree)上的權重若是距離，就可以求從某一個起始節點到終止節點的最小路徑。這可以運用到現今的物流運輸。兩個節點間的箭頭表示行進的方向。如下圖，請問從起始節點1到終止節點7，最短的路徑，下列何者正確？ (A)最短路徑距離總和19 (B)節點4到節點3是路徑的一部分 (C)節點3到節點5是路徑的一部分 (D)包含起始節點跟終止節點，共經過6個節點。[112初考資處]

最短路徑①→②→③→⑥→⑤→⑦，距離總和=4+1+4+1+6=16

 

【C】45.下列依據由左至右順序來建構二元搜尋樹(binary search tree)，那一個建構的樹有最大的深度(depth)？ (A)23, 7, 31, 40 (B)23, 31, 7, 40 (C)40, 7, 31, 23 (D)40, 23, 7, 31。[112國安五等]

(A)3層  23  /  \ 7   31      \      40

(B)3層  23  /  \ 7   31      \      40

(C)4層，深度最大  40  / 7   \   31    /  23

(D)3層  40  /  \ 7   23      \      31

 

【C】46.已知某二元樹為不同數字之最大堆積(Max-heap)，下列敘述何者正確？ (A)若以陣列(Array)來存放此二元樹，則此陣列中的元素必為遞減數列 (B)若以陣列來存放此二元樹，則此陣列中的元素必為遞增數列 (C)每一從樹根(Root)至樹葉(Leaf)的路徑(Path)上的元素必為遞減數列 (D)不會有上層(Level)任一元素比下層任一元素(不見得具有直屬關係)小的情形發生。[112普考電子]

(A)(B)若以陣列來存放二元樹，元素會依據二元樹的結構來排列。

(D非直屬關係，有可能發生。

 

【C】47.假設有一棵完滿二元樹(Full binary tree)含有n個內部節點(Internal nodes)，則該棵二元樹的總節點數是多少個？ (A)n+1 (B)2n-1 (C)2n+1 (D)log(n)，(log以2為底)。[112普考電子]

內部節點數 = n

葉節點數 = n + 1

總節點數 = n + (n + 1) = 2n + 1

 

【C】48.高度為3的AVL樹(只有一個節點的AVL樹高度為1)，總節點數最多為 (A)3 (B)5 (C)7 (D)8。[112鐵路員級]

AVL樹總節點數最多 = 2^H - 1 = 2³ - 1 = 7

 

【C】49.下列那種樹狀結構，其樹根到每個葉節點的路徑都會一樣長？ (A)AVL樹(AVL-tree) (B)二元搜尋樹(Binary Search Tree) (C)B樹(B-tree) (D)四叉樹(Quadtree)。[112鐵路員級]

B樹：從樹根到每個葉節點的路徑長度(高度)都是同一個值。

 

【C】50.下圖中的最小生成樹(Minimum Spanning Tree)其邊之總長為何？ (A)25 (B)26 (C)27 (D)28。[112鐵路員級]

3+4+4+3+4+3+3+3=27

 

【D】51.在一個空的二元搜尋樹(Binary Search Tree)中，依序插入值為5、4、1、3、2之節點後，則值為2之節點到根節點(Root)，需經過多少條邊(Edge)？ (A)1 (B)2 (C)3 (D)4。[112鐵路員級]

 

【B】52.假如一棵二元樹的8個節點分別以A-H表示，已知後序走訪的結果依序是FECBGDHA，而中序走訪的結果依序是FECAHBDG，則下列那一個節點是樹葉節點？ (A)節點A (B)節點B (C)節點C (D)節點D。[113初考資處]

FEBG是樹葉節點