高點102 關地務方來勝 版權所有, 重製必究! 資料結構 < 王致強老師精選 > 頭號重點 1 最近二年三等 / 四等地方政府特考重要命題方向 由最近二年 ( 年至 年 ) 之三等地方政府特考以及今年 ( 年 ) 相關國家考試的 資料結構 考題, 就其命題方向所鎖定的資料結構內容, 整理如下表 : 102 高考 專技 專利 交通 高考 關務 司法 專技 地特 關務 交通 高考 司法 公務 時間複雜度 陣列 鏈結串列 堆疊 佇列 運算式處理 字串比對 遞迴程式 二元樹基礎 二元樹追蹤 二元搜尋樹 互斥集合 堆積 AVL 樹 Trie 圖形表示法 圖形搜尋法 圖形生成樹 最短路徑 遞移封閉矩陣 AOE 網路 排序法 外部排序 樹搜尋法 搜尋法 雜湊法 霍夫曼碼 頭號重點 2 最近二年不同於地方政府特考之高普考重要命題方向 考生除了掌握上述有關近年地方政府特考的重點內容與方向外, 值得地方特考考生額外注意的是, 由於高普考與特考之典試委員身分的重疊性, 高普考 資料結構 考題的重點方向與內容, 也常特別值得參考 歷年 ( 近年 ) 命題重點較集中在 (1) 鏈結串列 (2) 堆疊 佇列的應用 (3) 遞迴 (4) 搜尋樹結構 (5) 堆積結構 (heap) 等 而今年國考的試題則著重在搜尋樹與堆積結構, 意謂著準備時須注意各種較新的資料結構的應 3-1
用, 才可能取得較好的成績 同學準備地方特考時, 宜特別注意 102 年各考試的趨勢 頭號重點 3 考前重點複習 ( 一 ) 中置式到後置式的轉換 1. 優先次序表 (Precedence Table) 在運算式的轉換中所需的資料結構, 主要是一個運算子優先順序表, 用來表示各運算子間的相對優先順序 所謂 " 相對 " 優先順序不只要表現運算子之間的優先順序, 也必須考慮到結合性 symbol F(ISP) G(ICP) 註解 ( 0 6 4 5 右結合性 *,/ 4 3 左結合性 +,- 2 1 左結合性 ) 6 來0 # -1-1 代表中序式開頭與結尾 2. 堆疊 : 用來記錄優先次序較低, 且尚未輸出的運算子 3. 中置式到後置式的轉換原則 : (1) 由左而右逐一讀取出中序式符號, 轉換成為後序式 (2) 當輸入為運算元時, 直接輸出至後序式 (3) 當輸入為運算子時, 則與堆疊頂端的運算子比較優先次序, 並將優先等級較高的運算子自堆疊取勝出, 並輸出至後序式 然後繼續比較, 直到輸入運算子優先序高於堆疊頂端之運算子時, 將輸入運算子置入堆疊中 (4) 當輸入為左括號時, 直接將左括號置入堆疊中 (5) 當輸入為右括號時, 將堆疊中之運算子逐一取出並輸出至後序式, 直到堆疊頂端為左括號時, 再將左 右括號一起丟棄 4. 後序式求值計算 (Evaluation of Postfi Epression) 處理原則 (1) 由左而右處理後序式 (2) 遇到運算元時, 置入堆疊中 (3) 遇到運算子時, 步驟如下 : A. 由堆疊中取出所需之運算元 B. 計算出結果 C. 將結果放回堆疊 (4) 最後在堆疊中只剩下一項資料, 即為最後結果 ( 二 ) 二元搜尋樹 1. 二元搜尋樹的定義二元搜尋樹是一棵二元樹, 樹根的左子樹中的節點皆小於樹根, 樹根的右子樹中的節點皆大於樹根 而且左 右子樹也都是二元搜尋樹 2. 二元搜尋樹的插入方式 (1) 遞迴法 : void BST_Ins(datatype, treeptr &t); { if (t == NULL) { t=(treeptr)malloc(sizeof(struct node)); t data = ; t lchild = NULL; t rchild = NULL; else if ( < t->data) BST_ins(, t->lchild); 3-2
高點p() 來p() 勝z 版權所有, 重製必究! else if ( > t->data) BST_ins(, t->rchild) (2) 二元搜尋樹的插入時間若原來的二元搜尋有 n 個節點, 插入一項新資料的時間複雜度為 O(1)~O(n);worst case 時間為 O(n), 可能發生在 skewed binary tree 時 ;average case 為 O(logn) 3. 二元搜尋樹中要刪除資料 時 : 可以使用下面程序來進行 先搜尋節點, 再依不同狀況來進行處理 原則如下 : (1) 若 為樹葉, 則直接刪除即可, 其父節點 p() 原先指向 的指標改為空指標 p() (2) 若 的 degree=1 時, 可以取其子節點來替代 刪除 之後, 節點被釋放, 而將父節點原先指向 的指標, 改成指向 的 ( 左或右 ) 子節點 z (3) 若 的 degree=2 時, 先找出 的中序前行節點 (inorder predecessor) 或後繼節點 (successor), 假設以 y 來表示, 先將節點 y 的資料拷貝到節點, 並將問題轉換成為刪除節點 y, 然後遞迴處理下去 y y (4) 時間複雜度 :O(1)~O(n),average case 為 O(logn) ( 三 ) 算式樹 1. 算式樹的定義 (epression tree) 算式樹是一個 binary tree, 若非 empty tree, 則 root 可以是 operand, 其左 右子樹皆為 empty tree; 若 root 為 operator, 則其左 右子樹則為非空的 epression tree 2. 算式樹與運算式之間的關係 (1) 對算式樹進行 pre-order traversal, 可以得到其所表示之 prefi epression 3-3 y p()
(2) 對算式樹進行 post-order traversal, 可以得到其所表示之 postfi epression (3) 對算式樹進行 in-order traversal, 卻未必可以得到其所表示之 infi epression 主要是因為可能需要另外再加上一些括號, 才能呈現與算式樹相同的運算順序 ( 四 ) 堆積結構 (Heaps) 1. 堆積的定義 (1) 最小堆積 (Min heap) 必須具備兩條件 : A. 最小堆積是一棵完全二元樹 (complete binary tree) B. 最小堆積是一棵最小樹 (min tree) [ 每個節點 其子節點 ] (2) 最大堆堆 (Ma heap) 必須具備兩條件 : A. 最大堆積是一棵完全二元樹 (complete binary tree) B. 最大堆積是一棵最大樹 (ma tree) [ 每個節點 其子節點 ] 2. 堆積的主要用途 (1) 堆積排序 (Heap Sort): 利用堆積來改善選擇排序法的效能 (2) 優先權佇列 (Priority Queue) : 使用 ma heap 來可以支援運算 Insertion 及 Delete the largest element( 即 delete-ma), 可以使兩個運算時間皆在 O(logn) 內完成 3. 插入新資料運算 (Insertion into a ma heap) (1) 將要插入的資料先加到陣列的尾端, 然後進行 bubbling 處理 (2)bubbling 處理 : 若資料不是 root, 則與其 parent 比較, 若大於其 parent 時, 與其 parent 互換, 然後往 root 方向繼續比較, 直到其小於或等於 parent ( 或新的資料已到達 root) 為止 (3) 所需之時間為 O(logn), 因為調整的步驟不會超過 heap 的高度, 而 heap 是 n 個節點的 complete binary tree, 其高度為 log 2 n + 1 勝(4) 實作如下 void Insert(data heap[], data, int &n) { int i; heap[i=++n]=; while (i!=1) { if (heap[i]<=heap[i / 2]) i=1; else { swap(heap[i], heap[i/2]); i/=2; 4. 刪除最大元素運算 (Delete the largest element from a ma heap) (1) 最大的資料在 root, 先將其取出 (2) 由陣列尾端取出一項資料, 開始從 root 進行由上而下之調整 (sift 動作 ) (3)sift 處理 :( 若 child 存在 ) 先找出其較大的 child, 若其比該資料項大, 則與將資料與此 child 互換, 然後繼續再調整下去, 直到 child(ren) 比其小或已經到樹葉為止 (4) 時間為 O(logn), 因為調整的步驟不會超過 heap 的高度, 而 heap 是 n 個節點的 complete binary tree, 其高度為 log 2 n + 1 (5) 實作如下 void DeleteMa( data heap[ ], data &, int &n) { int i, j; if (n==0) error(); =heap[1]; heap[1]=heap[n--]; i=1; j=2; while (j<=n) 3-4
{ 高點i=j; 版權所有, 重製必究! if (j<n) if (heap[j]<heap[j+1]) if (heap[i]>=heap[j]) j=n+1; else { swap(heap[i], heap[j]); j=2*j; j++; 5. 將二元樹調整成堆積的方法 void sift(int a[], int i, int n) { // 由第 i 個位置開始向下調整, 但調整不超過第 n 項 int temp, j; temp=a[i]; j=2*i; while (j<=n) { if (j<n&& a[j]<a[j+1]) j++; if (temp>a[j]) break; a[i]=a[j]; i=j; j=2*i; a[i]=temp; time = O( depth ) 主程序 void HeapSort(int a[], int n) { int i; for (i=n/2; i>=1; i--) sift(a,i,n); time = O(n), n 為二元樹的節點個數 ( 五 ) 霍夫曼演算法 (Huffman Algorithm) 1. 原理 : (1) 開始時, 每個外部節點皆各自建立一棵獨立的二元樹 (2) 然後, 重覆下列二步驟 (3) 自 L 中取出兩個 weight 最小的 trees (4) 將這兩棵樹加以合併, 重新計算他們的 weight 總和, 然後再加回 L 2. 演算法 :Huffman Algorithm (1) L Empty Min Heap; (2) for i l to n-1 do (3) begin (4) T AllocateNode(); (5) LeftChild[T] DeleteMin(L); // min-heap Delete-min (6) RightChild[T] DeleteMin(L); // min-heap Delete-min (7) Weight[T] Weight[LeftChild[T]]+Weight[RightCHild[T]]; (8) InsertMinHeap(L, T); // min-heap Insertion (9) end 3. 資料結構 (1) 使用 Min-Heap 來記錄樹的集合 (2)DeleteMin(L) : 從 L 中取出一個 weight 最小的 tree, 並將他由 L 中 delete 掉 (3)InsertMinHeap(L,T): 將合併後新產生的 tree T 加入 L 中 來勝3-5
高點來勝(vi,v j) (vi,v j) 2 ) 版權所有, 重製必究! 4. 時間分析 (1)DeleteMin, Insert 可以使用 min heap 的 delete-min 與 insertion 兩個動作來實作, 故兩者之 time compleity 皆為 O(logn) (2)for loop 的次數為 n-1 次, 故整個演算法的總時間為 O(nlogn) ( 六 ) 應用 : 霍夫曼碼 (Huffman Code) 1. 目的 : 為縮短訊息的總長度, 而採用的一種非固定長度的編碼方式, 根據各符號出現之頻率 ( 機率 ), 頻率較高者編碼長度較短 ; 而頻率低者編碼長度較長 2. 編碼方式 : 採用霍夫曼演算法 (Huffman's Algorithm) 先建立 Huffman Coding Tree, 若有 n 個基本符號 s1,s2,...,sn, 其編碼方式如下 : (1) 先找出所有符號的頻率 (2) 合併頻率最低的兩個, 其頻率相加 (3) 重覆步驟 (2), 合併到只剩下一個為止 (4) 根據合併之關係, 對每一次合併的兩項分別配置一個 bit, 一個配置 "0"; 另一個配置 "1" 3. 解碼方式 : 利用編碼所建立的編碼樹解碼 4. 霍夫曼碼是所有編碼方式中, 訊息編碼平均長度最短的一種 平均編碼長度可用公式 tq 計算, 其中 qi 為 si 的機率 (1 i n), 而 ti 為 si 的編碼長度 (bits 個數 ) 5. 統計編碼法平均編碼長度的理論下限為 q log q, 其中 S 為符號集 (symbol set) S 2 ( 七 ) 圖形表示法 1. 鄰接矩陣 (Adjacency Matri), 若圖形 G 有 n 個頂點, 以一個 n n 的矩陣 M 來表示 G, 如下 : 1 表示 E(G) M[i, j] = 0 表示 E(G) 所需的儲存空間 :O(n 2. 鄰接串列 (Adjacency List) (1) 每個頂點皆建立一個鏈結串列來記錄其鄰接頂點, 並且以 n 個首節點來記錄這 n 個串列的開頭位置 其 C 語言之宣告如下 : typedef struct node * nodeptr; struct node { datatype verte; nodeptr link; ; nodeptr head[]; (2) 第 i 個串列中, 記錄與頂點 Vi 相鄰的頂點 (3) 要點 : 鄰接串列空間需求 : 假設 n= V,e= E A. digraph: 共需要 n 個 head nodes, 以及 e 個 list nodes, 空間複雜度為 O(n+e) B. undirected graph: 共需要 n 個 head nodes, 以及 2e 個 list nodes, 空間複雜度亦為 O(n+e) 3. 適用性 (1) 稀疏圖形 : 使用. 鄰接串列較適合 (2) 密集圖形 : 使用. 鄰接矩陣較適合 ( 八 ) 圖形伸展樹 1. 伸展樹的特性 (1)Connected Graph 若有 n 個 vertices, 則 edges 個數 e n-1 (2)Acyclic Graph 若有 n 個 vertices, 則 edges 個數 e n-1 (3) 一個 graph 若有 n 個 vertices, 若取其中的 n-1 個 edges 形成一個 acyclic connected subgraph( 即 tree), 則此一 subgraph 即為來 graph 的 spanning tree (4) 一個 graph 若有 n 個 vertices, 若取 n-(connected components 的個數 ) 個 edges, 形成一個 acyclic subgraph( 未必是 connected), 則此一 subgraph 即為原來 graph 的 spanning forest n i= 1 i i 3-6
(5) 以 DFS 與 BFS 搜尋皆可以產生 spanning trees (6)minimal cost spanning tree: 在一個 weighted graph 中, 具有最小 weights 總和的 spanning tree 2. Kruskal s 最低成本伸展樹 (1) 演算法 T Φ; while T 中少於 n-1 個 edges 且 E is not empty do begin (v,w) E 中 weight 最低的 edge; delete (v,w) from E; if (v,w) 不會造成 T 中的迴路 then add (v,w) to T else discard (v,w) end; if T 中的 edges 數少於 n-1 then not_found; (2) 實作使用的資料結構 A. 使用最小堆積選擇 weight 最小的 edge B. 以 disjoint sets 的 tree representation 來檢查是否產生 cycle (3)Kruskal s 演算法的總時間 : O(elog e + elog n) = O(elog e) = O(elog n) 3. Prim s 最低成本伸展樹 (1) 演算法 v select a verte from V; U {v; while U V do begin find the minimum cost edge (u,v) where u in U and v in (V-U); add v to U; end; (2)Prim's 演算法的總時間 :O(n 2 ) ( 九 ) 最短路徑 1.Dijkstra s 演算法 (1) 演算法原則 A. 由 V-S 中選擇一個 dist 值最小的頂點 u B. 將頂點 u 加入 S 來勝C. 檢查頂點 u 所發出的每一個邊 (u,w), 若 w S, 則計算下式 dist[w] min{dist[w],dist[u] + cos t[u, w] (2) 條件 : 圖形不允許有負值的邊 (negative edges) (3) 時間 :O( V log V + E ) 2.Floyd-Warshall 演算法 (1) 原理將圖形中的頂點編號為 1~n, 令 A k (i,j) 表示由 i 到 j 的最短路徑長度, 但是只袝件經由編號 1~ k, 不能經過比 k 大的頂點 A. 起始值 :A 0 (i,j) 為 i 到 j 的直接距離 B. 目標是要求 :A n (i,j) 為 i 到 j 的最短路徑, 可以經由 1~n 任意頂點 C. 遞迴式 :A k (i,j) = min{a k-1 (i,j),a k-1 (i,k)+a k-1 (k,j) (2) 適用性 : 圖形允許有 negative edge(s), 但不能有 negative cycle (3)Floyd-Warshall 的時間複雜度 :θ( V 3 ) ( 十 ) 排序法各種排序法必須要熟悉運作方式以及程式, 另外排序法的特性也要注意 3-7
類別名稱最佳狀況最差狀況平均狀況 基本排序法 進階排序法 分佈式排序法 插入排序 Insertion 氣泡排序 Bubble 選擇排序 Selection 計數排序 Counting 快速排序 Quick 合併排序 Merge 堆積排序 Heap MSD 桶子排序 LSD 桶子排序 Distributive Counting 分佈計數排序 O(n) 排序好的資料 O(n) 排序好的資料 O(n 2 ) 反轉的資料 O(n 2 ) 反轉的資料 O(n 2 ) O(n 2 ) O(n 2 ) O(n 2 ) O(n 2 ) O(n 2 ) stable O(n) O(nlogn) O(n 2 ) 排序好的資料 來勝穩定排序 額外儲存體求量 O(n 2 ) stable a little O(n 2 ) stable a little O(nlogn) 視實作方式而定 unstable a little O(log n) ~(n) O(nlogn) O(nlogn) O(nlogn) stable O(n) O(nlogn) O(nlogn) O(nlogn) unstable a little O(nlogn) 平均分佈資料 O(nk) 資料分佈不均 O(nk) 視實作方式而定 O(n) O(k(n+b)) O(k(n+b)) O(k(n+b)) stable O(n+b) O(m+n) O(m+n) O(m+n) stable O(m+n) ( 十一 ) KMP 字型比對法 1. 使用 prefi function(failure function) 來加速 pattern 的移動 P[i] 的 Prefi function 定義如下 (0 < i m): π[i]=ma{ k : k<i 且 P[1..k]=P[i-k+1..i] 2. 當比對過程中, 發生 P[i] S[j] 狀況時, 可以取 P[π[i-1]+1] 與 S[j] 繼續比對下去, 就是將 pattern 一次向右移動 i-π[i-1]-1 個位置, 如此可以減少不必要的比對動作, 以加快對的速度 比對所需之時間為 O(m+n) 3.KMP 字型比對 algorithm n length(s); m length(p); compute prefi function π; i 1; j 1; while j-i n-m do begin if i>1 and P[i] S[j] then i π[i-1]+1 else if P[i]=S[j] then end; begin i i+1; j j+1; else j j+1; if i>m then begin print position j; i π[i-1]+1 end; end; 3-8
( 十二 ) 2-3-4 tree 1. 2-3-4 tree 是一棵搜尋樹, 可以是 empty tree 或者符合下面條件 : (1) 每個 node 為 2-node 3-node 或 4-node (2) 是一棵 B-tree 2. 2-3-4 tree 的 Forward insertion: 在進行 insertion 運算時,2-3-4 tree 要比 2-3 tree 來得方便, 只要由 root 到 leaf 進行一個 pass, 即可完成 (1) 當由 root 做 top-down search 時, 遇到 4-node 先行 split, 從樹根一路向下直到樹葉 (2) 在樹葉中將資料存入之後, 就不用再做任何處理 3. 2-3-4 tree 的 Forward deletion: 在進行 deletion 兩運算時,2-3-4 tree 也比 2-3 tree 來得方便, 也是只要由 root 到 leaf 進行一個 pass, 即可完成 (1) 為了避免 backward combine, 在 top-down search 時, 遇到 2-node 時, 即先轉換成 3-node 或 4- node 轉換 2-node 分分三種狀況處理 : (a) 其 sibling 皆為 2-node => 將 node 與一個 sibling 以及 parent 中的一個元素合併 (b) 有 sibling 為 3-node 或 4-node => 由 sibling 中借一個元素過來 來(2) 最後在樹葉進行 deletion 即可 (3) 若要刪除的資料在內部節點, 須找中序前行節點或後續節點進行轉換, 再行刪除 ( 十三 ) red-black tree 1. red-black tree 的重要特性 :red-black tree 與 2-3-4 tree 的關係 : 在 2-3-4 tree 中同一個節點的資料, 在 red-black tree 中會獨立成為節點, 這群原屬 2-3-4 tree 中同一節點的 red-black tree 節點, 會具有相同的 rank (1) red node: 與 parent 的資料在原來 2-3-4 tree 勝中屬於同一個 node (2) black node: 與 parent 的資料在原來 2-3-4 tree 中不是同一個 node (3) red-black tree 是一棵 binary search tree 2. red-black tree 必須滿足下面特性 : 每個節點可以是 red node 就是 black node (1) root 一定是 black node (2) 所有的 leaves(eternal node) 皆為 black nodes (3) 一個 red node, 其 children 皆為 black node (4) 每個節點到其後代 leaves 的每一條路徑上, 皆包含相同數目的 black node 3. red-black tree 的處理, 可參考對應 2-3-4 tree 的規則進行 ( 十四 ) 對稱最小最大堆積 (SMMH, Symmetric Min-Ma Heap) 定義 :SMMH 是一棵完全二元樹, 除了樹根不存資料外, 其餘每個節點皆儲存一個元素, 故存有 n 個元素的 SMMH 會有 n+1 個節點 若 為 SMMH 中的某個節點, 令 S() 是以 為樹根的子樹中, 除了節點 以外的其他節點集合, 則下面兩條件成立 : 的 left child Lchild() 是 S() 中最小的元素 的 right child Rchild() 是 S() 中最大的元素 範例 : 一個 SMMH S(11) 7 79 11 73 8 52 15 35 21 39 13 47 S(79) 3-9
要點 :SMMH 的特性 (1) 每個節點,Lchild() Rchild() y S() (2) 每個節點, 對任一個,y Lchild() (3) 每個節點, 對任一個 y S(),y Rchild() 要點 :SMMH 的 Insertion 運算 (1) 將完全二元樹的節點增加一個, 置入插入的資料 (2) 若 有 left sibling y, 且 y >, 則將 y 與 對調 (3) bubble-up pass, 以 gp() 代表 的 grand parent: (a) 若 Lchild(gp())>, 則對調 Lchild(gp()) 與 (b) 若 Rchild(gp())<, 則對調 Rchild(gp()) 與 (4) 重複 (3), 直到沒有 (a) 或 (b) 情況為止, 結束處理 範例 :Insert 3 的例子 來勝gp() 7 79 Lchild(gp()) 11 73 8 52 15 35 21 39 13 47 3 8>3 進行 3.(1) 處理 Lchild(gp()) gp() 7 79 11 73 3 52 15 35 21 39 13 47 8 7>3 進行 3.(1) 處理 3 79 11 73 7 52 15 35 21 39 13 47 8 結束處理要點 :SMMH 的 Deletion Min 運算 (1) 將 h[2] 取出, 由 h[n+1] 取出為 置於 h[2], 令節點個數 n 減少 1 (2) 令 y 代表 min{lchild(),lchild(sibling(): 分三種狀況處理 (a) 若 y>, 則結束處理 3-10
(b) 若 y<, 則將 y 與 交換, 繼續 2 (c) 若 已無 child 而有 left sibling z, 若 z>, 則將 與 ztgdi yrbgr, 然後結束處理 範例 :Delete-min(delete 3) 的例子 3 79 11 73 7 58 15 35 21 39 13 47 8 52 刪除最小的 3(h[2]) 後, 取出最後一個節點 52, 置於 h[2], 以 表示 Lchild() 52 79 Lchild(sibling()) 11 73 7 58 15 35 21 39 13 47 8 min{lchild(),lchild(sibling())=7<52=, 將 52 與 7 對調 來勝7 79 11 73 52 58 15 35 21 39 13 47 8 Lchild() min{lchild(),lchild(sibling())=8<52(=), 將 52 與 8 對調 7 79 Lchild(sibling()) 11 73 8 58 15 35 21 39 13 47 52 52 已無子節點亦無 sibling, 結束 3-11