地方特考資訊處理資料結構考試準備方法重點總複習

2020/04/10
地方特考資訊處理資料結構考試準備方法重點總複習
不用擔心地方特考資訊處理資料結構如何準備,常考考點、易錯題目,這邊都幫你做了篩選和彙整囉!題題皆附上詳細解析,同學們最容易搞混的觀念全部都幫你打通~考前高效總複習這樣做就對了!

資料結構(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分)