資訊處理 107 年資料結構考古題

計算正整數a 和b 的最大公因數gcd(a, b)的演算法，以類似C 語言表示 如下: 1 integer gcd(a, b) {

若已知一個二元樹（binary tree）的節點數（node）總共有305 個，且有104 個樹葉 節點（leaf node），試求出分支度（degree of branch）為1 的節點數有多少個？（10 分）

請說明並比較二分搜尋（binary search）與一般二元搜尋樹（binary search tree）兩 者在儲存鍵值並應用來進行搜尋鍵值功能時，在'建置'與'搜尋'程序上作法與效能的 差異（13 分）。 若有n 個鍵值，以下列甲和乙兩種資料結構策略儲存： 策略甲：由小到大依序儲存在一陣列中 策略乙：以AVL tree 架構儲存 請以Big-O 觀念比較後續六種不同功能獨立運作時，這兩種策略何者效能較優或 兩者效能相近：尋找特定鍵值k；尋找排序為j 的鍵值；刪除特定鍵值k； 刪除排序為j 的鍵值；插入新鍵值；依序輸出所有鍵值。（12 分）

x = a; y = b;

已知一個二元樹（binary tree）的後序追蹤（postorder traversal）為FEACGHBD，而 中序追蹤（inorder traversal）為EFADCBGH，其中字母A 到H 分別代表一個節點的 名稱。 請畫出此二元樹。（10 分） 請寫出此二元樹的前序追蹤（preorder traversal）。（5 分） 請寫出此二元樹的廣度優先走訪順序（breadth-first traversal）。（5 分）

一非空的二元樹（binary tree），如果有n0 個葉節點（leaf node）且n2 個節點之分支 度（degree）為2，請證明n0 = n2+1。（25 分）

while (y > 0) {r = x % y; x = y; y = r;}

給定一權重圖（weighted graph）如下： 試寫出下圖的相鄰矩陣（adjacency matrix）及相鄰串列（adjacency list）。（10 分） 請使用Kruskal 演算法找出下圖的其一種最小生成樹（minimum spanning tree）， 並寫出最小生成樹的邊之建構順序。（15 分）

一無向圖G 之節點集合為G(V)={0,1,2,3,4,5,6,7,8,9}，邊集合為G(E)={(0,1), (1,2), (1,3), (2,4), (3,4), (3,5), (5,6), (5,7), (6,7), (7,8), (7,9)}；請列出G 之接合點（articulation point）和畫出G 的所有雙連通元件（biconnected component），雙連通元件須以節點 和邊構成之子圖方式表示。（20 分）

return x;

今有八個數字： 6、12、7、9、15、10、4、11 儲存於陣列中，由不同演算法進行遞 增排序。 請按照合併排序法（merge sort）步驟，列出此八個數字的順序變化過程。（10 分） 請按照快速排序法（quick sort）步驟，列出此八個數字的順序變化過程。（10 分） 如果輸入n 筆資料時，請寫出這二種排序法之時間複雜度以及空間複雜度。（10 分）

對稱式最小-最大堆積（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 分）

} 其中資料型態integer 表示整數，x % y 表示x 除以y 的餘數。請回答下 列問題：（每小題10 分，共20 分）  請證明：輸入任意兩個正整數，此程式執行一定時間後就會停止，不 會造成無窮迴圈。  假設a > b，請證明此程式之while 迴圈（第3 行）至多只會被執行 2 log2 b +1 次。 二、 給定一個權重圖（weighted graph），G =(V, E, w)，假設V = {1, 2,...,n}， 且每個邊（edge）e 的權重w(e)都是正整數。令l(v)為以v 為端點的所有 邊中權重最小的邊。將這些邊集合起來稱作L，也就是 。 ∪v l L = ) ( V v∈ （每小題5 分，共20 分）  假設每個邊的權重都不相同。請證明由L 中這些邊所構成的子圖（edge induced subgraph）G[L]沒有迴圈。  G[L]是否一定是G 的擴張樹（spanning tree）？若是請證明之，若不 一定是請給一個反例。  用以上之結論，設計一個計算G 的最小權重擴張樹（minimum spanning tree）的演算法。  在一般的應用中，邊的權重可能會相同，請修正上述之演算法，使修 正後之演算法可以正確找出答案。 三、 假設陣列A[1..n]儲存n 個正整數x1, x2,..., xn。（每小題10 分，共20 分）  已知所有的正整數xi ≤ M。請設計一個O(n + M )時間的演算法將這些 整數由小到大排列。  已知所有的正整數xi ≤ n2。請設計一個O(n)時間的演算法將這些整數 由小到大排列，或證明這是不可行的。 四、 假設有個陣列A[1..n]儲存著n 個整數。可將A[1..n]看成二元樹，其中A[1] 是樹根。A[i]的左右子節點分別為A[2i]和A[2i + 1], i =1, 2, . . . , n/2。若 2i>n 或2i+1>n，則這些子節點是不存在的。若A 滿足A[i] ≥ max{A[2i], A[2i + 1]},1 ≤ i ≤ n/2，則稱陣列A[1..n]是一個堆疊（heap）。假設有個副 程式sift(A, r, n)其輸入參數A 是一個陣列，n 是A 的大小，r ≤ n 是一個 指標，指向此子樹的樹根。副程式sift(A, r, n)的功能是將A[r]為樹根的 子樹變成heap。在呼叫sift(A, r, n)之前，它的左右子樹都已經是heap。 副程式sift(A, r, n)所需的計算時間是O(h(r))，其中h(r)是以A[r]為樹根 的子樹的高度，也就是從樹根到任一樹葉的最長距離。 （每小題10 分，共20 分） 用sift(A, r, n)設計一個線性時間的演算法，將陣列A[1..n]變成heap。 分析以上所設計演算法的計算複雜度為O(n)。 五、斐波納契數（Fibonacci number）Fn的定義是F0 = 0, F1 = 1, Fn = Fn－1+ Fn－2, n> 1。 計算Fibonacci number Fn 的演算法，以類似C 語言表示如下： 1 integer f [N]; // array of N integers 2 integer F(n) { 3 if ( f [n] < 0) 4 f [n]= F(n－1)+ F(n－2); 5 return f [n]; 6 } 7 integer Fib(n) { 8 f [0] = 0; f [1] = 1; 9 for (i = 2; i ≤ n; i = i + 1) 10 f [i]=－1; 11 return F(n); 12 } 其中資料型態integer 表示整數。假設輸入的整數n>1。主程式執行 Fib(n)，則副程式F(n)第4 行之指令： f [n]= F(n－1)+ F(n－2)會被執行幾次？請說明理由。（20 分）

請使用虛擬碼（pseudocode）或C 語言或C++語言撰寫程式片段。 以遞迴的呼叫方式寫出二元搜尋法（binary search）。（10 分） 根據所寫的虛擬碼或程式碼，寫出二元搜尋法之時間複雜度。（5 分）