不用擔心地方特考資訊處理資料結構如何準備，常考考點、易錯題目，這邊都幫你做了篩選和彙整囉！題題皆附上詳細解析，同學們最容易搞混的觀念全部都幫你打通~考前高效總複習這樣做就對了！
【資料結構】(108地方特考考前重點整理)
一、請回答下列問題：
舉例解釋甚麼是“先廣後深搜尋”（Breadth first search）。
舉例解釋甚麼是“Kruskal 的最小花費擴張樹（Minimum cost spanning tree）”演算法。
【擬答】：
選擇一個頂點V做起始點，然後依序走訪所有與V 相鄰且尚未走訪的頂點，直到沒有相鄰的頂點或都已經走訪過再走訪下一層。
準備一個佇列 Q。
將起始頂點 v 加入到 Q 之中（Enqueue）。
若 Q 不是空的，則執行下列步驟，否則跳到步驟 4：
3-1 從 Q 取出一頂點 w（Dequeue）。
3-2 將 w 標示為『已拜訪過』。
3-3 將所有與 w 相鄰且尚未標示『已拜訪過』的頂點加入到 Q 之中（Enqueue）。
3-4 回到步驟 3。
結束:
例如在下列圖形中的BFS搜尋過程就是ABCDEFGI
每次從邊的集合中選取值最小者，如果加入此邊不會產生cycle就加入此邊，如此繼續直到所有頂點都被連上為止。Kruskal演算法的時間複雜度為O(e log e) 或者是O(n2 log n)，因為e=O(n2)。
令花費最少擴張樹 T=ψ。
從E中選取花費最少的邊(VX ,VY)。
如果(VX,VY)不會使T產生迴路則將之加到T中；否則，自E中刪除之。
重複步驟2、3，直到T的邊數等於 N-1 為止。
二、請以遞迴方式，使用C語言寫出︰
欲尋找兩數（m與n）之間的最大公約數（GCD）的副程式：int gcd（int m, int n）。
費式數列（Fibonacci Number）的副程式int Fibonacci(int n)。
三、以下為前序追蹤（Preorder Traversal）及後序追蹤（Postorder Traversal）的順序：
前序追蹤順序：M, N, I, A, H, J, G, B, C, F, K, L, E, D, Y
後序追蹤順序：A, H, I, B, C, G, F, J, N, E, D, L, Y, K, M
請畫出此二元樹。
請寫出此二元樹的中序追蹤（Inorder Traversal）順序。
四、請將下列中序表示式(a + b) * c – (d + e * f / ((g / h + i – j) * k)) / l轉換如下的表示式︰
後序表示(postfix notation)。
前序表示(prefix notation)。
五、將下列資料依序輸入，以所指定的資料結構呈現結果：
Dec, Jan, Apr, Mar, Jul, Aug, Oct, Feb, Sep, Nov, Jun, May
其中字串大小依英文字母順序決定，亦即 A＜B＜…＜Z，a＜b＜…＜z。
二元查詢樹(binary search tree)。
最大累堆(max-heap)。
六、二元樹（binary tree）
有一個二元樹（binary tree）的中序走訪（inorder traversal）順序為ABCDEFGHI，它的後序走訪（postorder traversal）順序為BACFEIHGD，其中每個英文字母代表一個節點。請畫出此二元樹。
上述二元樹的前序走訪（preorder traversal）順序為何？
在二元搜尋樹（binary search tree）中，那一個走訪順序（前序、中序或後序）正好為排序好的情況？原因何在？（本小題未寫明原因者，不給分）
如何利用線性掃瞄方式，判斷一個前序運算式（prefix expression）是否合法？
七、假設有下列數種排序方法：(A)bubble sort (B)quick sort (C)heap sort (D)merge sort (E)radix sort (F)insertion sort。回答下列問題時，請分別以ABCDEF之代號答之。
一個排序法，在輸入資料中有多筆相同資料時，於排序前與排序後，任兩筆相同的資料前後順序不變者，稱之為「穩定排序法」。請問那些排序法為穩定排序法？
假設輸入資料有n個，在最糟情形下，那些排序法的時間複雜度為（nlogn）？
排序程式實作時，那些排序法需要額外的陣列或鏈結串列？
在程式實作時，一般使用陣列進行排序。有些時候也需要對鏈結串列進行排序。那些排序法無法對單向鏈結串列（linearly linked list）進行排序？
【擬答】：
ADEF。
CD。
BDE。
C。
九、有關圖形與樹的名詞：
請說明何謂擴張樹（Spanning Tree）。
請說明何謂雙連通圖（Biconnected Graph）。
請說明何謂二分圖（Bipartite Graph）。
請說明每個樹是否均屬於二分圖。
請說明每一個高度平衡二元樹（AVL）是否均屬於完滿二元樹（Fully Binary Tree）。
十、假設我們要對一組訊息AAAAABBCCCDDDDE進行二進位數的編碼（Code）
每個字元編碼為相等長度，則此訊息進行編碼後，最少需多少位元？
若每個字元編碼為可變長度，則此訊息進行編碼後，最少需多少位元？
十一、有一個雜湊表（hash table），共有11個籃子（bucket），且每個籃子中可存一個鍵值(key)，假設雜湊函數為 h(x) = x %11，亦即除以11的餘數。今有8個鍵值：73, 25, 29, 33 , 51, 41, 20, 43。
請將此8個鍵值依次存入此雜湊表，並將結果的雜湊表畫出。
假設利用線性探測法（linear probing）來處理碰撞（collision）的問題。
假設現在要找鍵值43，請問需要做幾次鍵值的比較才能找到43？
假設現在要找鍵值64，請問需要做幾次鍵值的比較才能確定64不在雜湊表裡？
十三、今有一採用開放位址（open addressing）方式儲存鍵值，大小為14的雜湊表（hash table），其雜湊函數為Hi(k) = h1(k) + i h2(k) (mod 14)，i = 0, 1, …, 13,其中h1(k) = k (mod 14)。依序存入下列鍵值15、18、42、19、10、28、27、38、80、55。
設h2(k) ≣ 1，請列出最後雜湊表的結果與使用雜湊函數的次數。
設h2(k) = 1 + k (mod 13)，請列出最後雜湊表的結果與使用雜湊函數的次數。
十五、有下列的資料要進行由小到大的排序運算：
30, 20, 70, 90, 50, 60, 40, 80
請按下列方法，說明資料異動的情況。
氣泡式排序（bubble sort）。
快速排序（quick sort）。
【擬答】：
氣泡式排序（bubble sort）：
Initial:30, 20, 70, 90, 50, 60, 40, 80
Pass 1:20, 30, 70, 50, 60, 40, 80, 90
Pass 2:20, 30, 50, 70, 40, 60, 80, 90
Pass 3:20, 30, 50, 40, 60, 70, 80, 90
Pass 4:20, 30, 40, 50, 60, 70, 80, 90
Pass 5:20, 30, 40, 50, 60, 70, 80, 90，沒有改變故完成排序
快速排序（quick sort）:
Initial:30, 20, 70, 90, 50, 60, 40, 80
Pass 1:20, 30, 70, 90, 50, 60, 40, 80
Pass 2:20, 30, 60, 40, 50, 70, 90, 80
Pass 3:20, 30, 50, 40, 60, 70, 80, 90
Pass 4:20, 30, 40, 50, 60, 70, 80, 90
十六、關於最小成本展開樹（minimum cost spanning tree）的問題：
參考下圖，繪出最小成本展開樹。
試述最小成本展開樹在網路規劃的應用。
十八、對稱式最小-最大堆積（Symmetric Min-Max Heap，簡稱SMMH）是一種優先佇列（priority queue），請回答下列與SMMH相關的問題。
請說明SMMH特性並說明以SMMH建構之優先佇列與以一般的堆積（heap）建構之優先佇列功能有何不同？並從一個空的SMMH開始，依序插入30,20,50,5,4,9,70,2,80。請畫出最後SMMH的樹狀結構圖。（10分）
請畫出第小題建構的SMMH，刪除數字2後SMMH的樹狀結構圖。（5分）
請以一維陣列設計一資料結構儲存SMMH，該資料結構可以使節點透過其對應之陣列索引值x構成的數學式計算出其祖父節點g、父節點p、左子節點l、右子節點r與兄弟節點s等在陣列中的索引值。假設一維陣列之起始索引值為0，請列出由x構成之計算g、p、l、r、s的數學式。並請畫出以此一維陣列儲存第小題建構完成的SMMH的結果。（15分）
