阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 107年 - 107 鐵路高員三級 - 資料結構#69642
107年 - 107 鐵路高員三級 - 資料結構#69642
科目:
公職◆資料結構 |
年份:
107年 |
選擇題數:
0 |
申論題數:
11
試卷資訊
所屬科目:
公職◆資料結構
選擇題 (0)
申論題 (11)
一、若已知一個二元樹(binary tree)的節點數(node)總共有 305 個,且有 104 個樹葉 節點(leaf node),試求出分支度(degree of branch)為 1 的節點數有多少個?(10 分)
⑴請畫出此二元樹。(10 分)
⑵請寫出此二元樹的前序追蹤(preorder traversal)。(5 分)
⑶請寫出此二元樹的廣度優先走訪順序(breadth-first traversal)。(5 分)
⑴試寫出下圖的相鄰矩陣(adjacency matrix)及相鄰串列(adjacency list)。(10 分)
⑵請使用 Kruskal 演算法找出下圖的其一種最小生成樹(minimum spanning tree), 並寫出最小生成樹的邊之建構順序。(15 分)
⑴請按照合併排序法(merge sort)步驟,列出此八個數字的順序變化過程。(10 分)
⑵請按照快速排序法(quick sort)步驟,列出此八個數字的順序變化過程。(10 分)
⑶如果輸入 n 筆資料時,請寫出這二種排序法之時間複雜度以及空間複雜度。 (10 分)
⑴以遞迴的呼叫方式寫出二元搜尋法(binary search)。(10 分)
⑵根據所寫的虛擬碼或程式碼,寫出二元搜尋法之時間複雜度。(5 分)