計概16-06樹－統測試題

【四技試題】

【D】01.下列關於二元樹(Binary Tree)的敘述，何者正確？ (A)二元樹只能用鏈結串列(Linked List)儲存 (B)二元樹只能用陣列(Array)儲存 (C)二元樹的每個節點必須要有兩個分支 (D)二元樹的每個節點最多只有兩個分支。[111管理]

 

【B】02.灰姑娘跟王子認識之後，他們常去約會的六個景點及路線如圖所示，王子發現道路需要重新修繕，每條道路修繕的成本如圖線段上的數值所標示，若王子使用最小生成樹(Minimum Spanning Tree)演算法找出連接這六個景點道路的最低修繕成本，則此最低修繕成本為何？ (A)15 (B)16 (C)17 (D)18。[111管理]

 

【B】03.樹(Tree)是圖(Graph)的一種特例，假設樹的節點數量為V、邊(或分支)的數量為E，則關於V與E的敘述，下列等式何者正確？ (A)V＝E–1 (B)E＝V–1 (C)E＝V (D)V＝2×E。[111管理]

 

【C】04.有一個二元樹(Binary Tree)如圖所示，關於走訪此二元樹節點(Node)的敘述，下列何者正確？ (A)使用前序(Pre-order)、中序(In-order)、後序(Post-order)的走訪方式，所得到的結果序列相同 (B)使用前序(Pre-order)走訪會得到的序列為DCGAEHBFI (C)使用中序(In-order)走訪會得到的序列為ABCDEFGHI (D)使用後序(Post-order)走訪會得到的序列為BACDFEIHG。[111管理]

 

【B】05.一棵樹高為6層(Level)的二元搜尋樹(Binary Search Tree)，樹中每個節點(Node)的資料為數值，搜尋時最少比較幾次就能夠找到所要搜尋的數值？ (A)0 (B)1 (C)4 (D)6。[112管理]

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

 

【C】06.所有節點都向左子樹或右子樹歪斜稱為歪斜樹(Skewed Tree)，阿信將6個節點畫成歪斜樹，其最多層的層數為何？ (A)3 (B)4 (C)6 (D)8。[112管理]

歪斜樹：最多層數，即節點數6。


 【C】07.關於決策樹(Decision Tree)的敘述，下列何者正確？ (A)決策樹不屬於分類演算法，無法建立分類模型 (B)決策樹十分複雜且不容易解釋和理解，實用性有限 (C)決策樹能夠處理數值型和類別型資料，且資料必須事先標記(Labeling) (D)決策樹之分支判斷只有YES與NO兩種選項，因此無法處理複雜的問題。[113管理]

 

【B】08.電力公司擬建構最少成本的輸配電線路，是一個典型的最小生成樹(Minimum Spanning Tree)問題。參照圖所示之圖(Graph)資料結構，邊(Edge)所標數值為其成本(Cost)，此圖之最小生成樹總成本是多少？ (A)10 (B)11 (C)12 (D)19。[113管理]

 

【二技試題】

【A】01.下列有關資料結構的描述，何者不正確？ (A)B tree的資料結構不能儲存在硬碟中 (B)B tree的搜尋時間通常要比二元樹短 (C)遞迴是一種常常用來實作樹狀資料結構的程式設計方式 (D)AVL樹是一種在建構過程中左右子樹(subtree)能保時適當平衡的二元樹。[91管理]

 

【D】02.在一顆二元樹(binary tree)中，若分支度(degree)為0的節點有40個，則分支度為2的節點有幾個？ (A)10 (B)20 (C)29 (D)39。[92電機]

 

【C】03.有一棵二元樹，總節點數為100個，分枝度(branch factor)為1的節點數有41個，則分枝度為2的節點數有幾個？ (A)27 (B)28 (C)29 (D)30。[92管理]

 

【B】04.下列關於二元樹(binary tree)的敘述，何者正確？ (A)前序追蹤(preorder traversal)與後序追蹤(posrorder traversal)可以決定唯一的二元樹 (B)前序追蹤(preorder traversal)與中序追蹤(inorder traversal)可以決定唯一的二元樹 (C)二元樹的每個節點的分支度degree)必須為2 (D)若一棵完全二元樹(full binary tree)含有128個樹葉節點(leaf node)，則其總節點數為256個。[93電機]

 

【B】05.三個節點最多可以排成幾棵不同的二元樹？ (A)4棵 (B)5棵 (C)6棵 (D)7棵。[93電機]

 

【C】06.有300個節點的三元樹(ternary tree)，其最小高度(height)為何？(註：僅有一個節點的三元樹，其高度為1) (A)4 (B)5 (C)6 (D)7。[94管理]

 

【B】07.下列有關二元樹(binary tree)之敘述，何者錯誤？ (A)二元樹中的節點(node)數可為零 (B)完整二元樹(full binary tree)，若樹的高度為3，則此二元樹節點數為8 (C)二元樹的根節點(root)下可分成兩個子樹，稱為左子樹與右子樹 (D)二元樹中的節點至多只能有兩個子節點。[95管理]

 

【D】08.若樹(tree)高度的定義為根節點(root)的高度；節點(node)高度的定義為該節點至葉節點(leaf)的最長路徑(path)的長度；路徑長度的定義為路徑上節點的數目減1。對於鍵值(key)不得重複的二元搜尋樹(binary search tree)，若已知某個二元搜尋樹有40個節點，則下列敘述何者正確？ (A)該二元搜尋樹之高度至少為6 (B)該二元搜尋樹之高度至多為15 (C)若在該二元搜尋樹中尋找某個值，則至少需比對5個節點才有可能找到 (D)若在該二元搜尋樹中尋找某個值，且該值不一定存在於該二元搜尋樹中，則至多需比對40個節點才能確定結果。[96管理]

 

【C】09.一個網路圖如圖所示，其中的數字表示各邊(Edge)的權重(Weight)，則在此網路圖的「最小成本擴展樹」(Minimum Cost Spanning Tree)中，邊的權重總和為多少？ (A)9 (B)14 (C)15 (D)21。[98管理]

A-C-B-D-F = 1 + 3 + 4 + 7 = 15

 

【D】10.下列關於AVL Tree與B-Tree的敘述，何者正確？ (A)均是二元樹(Binary Tree) (B)均不是二元樹 (C)只有B-Tree是二元樹 (D)只有AVL Tree是二元樹。[98管理]

 

【D】11.有一棵二元樹，其分枝度(Branch Factor)為1的節點個數為12，分枝度為2的節點個數為26，則此二元樹的總節點個數為何？ (A)38 (B)63 (C)64 (D)65。[98管理]

 

【B】12.有一高度為5的二元樹，此二元樹最多可包含多少個節點？(假設僅有一個節點的二元樹，其高度為1) (A)15 (B)31 (C)32 (D)63。[99管理]

留言

張貼留言

這個網誌中的熱門文章

計概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.
閱讀完整內容