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 分）