阿摩線上測驗
登入
阿摩線上測驗
登入
樹結構與演算法完整大綱 - 國考重點整理 一、基本樹結構類型 1.1 一般樹 (General Tree) 定義：每個節點可有任意數量的子節點 特性：階層結構、無環路、連通圖 考點：樹的遍歷、高度計算 1.2 二元樹 (Binary Tree) 定義：每個節點最多有兩個子節點（左、右） 類型： 完全二元樹 (Complete Binary Tree) 滿二元樹 (Full Binary Tree) 完美二元樹 (Perfect Binary Tree) 考點：節點數公式、高度與節點關係 1.3 二元搜尋樹 (Binary Search Tree, BST) 定義：左子樹 < 根節點 < 右子樹 操作：搜尋、插入、刪除 時間複雜度：平均 O(log n)，最壞 O(n) 考點：BST性質驗證、操作實作 1.4 平衡樹 AVL樹 特性：任意節點的左右子樹高度差 ≤ 1 旋轉：LL、RR、LR、RL旋轉 時間複雜度：O(log n) 紅黑樹 (Red-Black Tree) 特性：節點著色、平衡性質 應用：STL map、set實作 1.5 堆積 (Heap) 最大堆積：父節點 ≥ 子節點 最小堆積：父節點 ≤ 子節點 實作：陣列表示法 應用：優先佇列、堆積排序 1.6 B樹與B+樹 B樹：多路搜尋樹，適合磁碟存取 B+樹：葉節點連結，適合範圍查詢 應用：資料庫索引 二、樹的遍歷演算法 2.1 深度優先搜尋 (DFS) 前序遍歷 (Preorder)：根→左→右 中序遍歷 (Inorder)：左→根→右 後序遍歷 (Postorder)：左→右→根 實作：遞迴或堆疊 2.2 廣度優先搜尋 (BFS) 層序遍歷 (Level-order)：逐層訪問 實作：佇列 (Queue) 應用：最短路徑、層次結構分析 三、重要演算法應用 3.1 圖論演算法 Dijkstra最短路徑演算法 策略：選擇距離最短的未訪問頂點 資料結構：最小堆積或優先佇列 時間複雜度：O((V+E)log V) 應用：網路路由、GPS導航 Prim最小生成樹演算法 策略：選擇權重最小的邊 資料結構：最小堆積 時間複雜度：O(E log V) 應用：網路設計、電路佈線 Kruskal最小生成樹演算法 策略：按邊權重排序，避免環路 資料結構：並查集 (Union-Find) 時間複雜度：O(E log E) 3.2 編碼演算法 Huffman編碼 目的：建構最優前綴編碼樹 策略：頻率最低的兩個節點合併 資料結構：最小堆積 應用：資料壓縮、通訊編碼 3.3 系統演算法 事件驅動模擬 策略：按時間順序處理事件 資料結構：優先佇列（以時間為優先權） 應用：作業系統排程、網路模擬 四、國考常見題型 4.1 樹結構分析 節點數、葉節點數、高度計算 完全二元樹性質應用 BST操作後結果 4.2 遍歷序列 給定兩種遍歷序列，重建樹結構 前序+中序 → 唯一確定 後序+中序 → 唯一確定 4.3 演算法實作 Dijkstra演算法步驟 Prim/Kruskal比較 Huffman編碼過程 4.4 時間複雜度分析 各種樹操作的時間複雜度 平衡樹vs非平衡樹性能比較 圖論演算法複雜度 4.5 應用題 最短路徑問題 最小生成樹問題 排程與優先權處理 五、記憶口訣 5.1 樹遍歷 前序：「根左右」- 先訪問根 中序：「左根右」- 根在中間 後序：「左右根」- 根在最後 5.2 演算法特色 Dijkstra：「貪婪選最近」 Prim：「貪婪選最輕」 Huffman：「頻率低先合」 5.3 複雜度記憶 平衡樹：O(log n) - 「對數時間」 非平衡樹：O(n) - 「線性時間」 圖演算法：O(E log V) - 「邊乘對數頂點」 六、考試重點提醒 樹的基本性質：節點數公式、高度關係 遍歷演算法：能手算遍歷結果 平衡樹操作：AVL旋轉、紅黑樹性質 圖論演算法：步驟、複雜度、應用場景 實際應用：能說明演算法在系統中的用途