所屬科目：公職◆資料結構
(一)若 e 是所有邊中權重最大者，則。（也就是 e 不會在任一個 G的最小權重擴張樹中）（10 分）
(二)假設 G 是 2-連通（2-connected）。（也就是去掉任一條邊 G 仍是連通的）此時，若 e 是所有邊中權重最大者，則。（15 分）
三、斐波那契數（Fibonacci number）Fn的定義為：F0 = 0, F1 = 1, Fn= Fn-1 + Fn-2 ,n ＞ 1。下面是一個計算斐波那契數 Fn 的演算法，以類似 C 語言的函數（C function）表示，其中資料型態 integer 表示整數。 假設輸入的整數 n≧0。證明此程式的計算複雜度 T(n) ＞ Fn。在分析計算複雜度時，可將“==”, “=”, “+”和“return”當作只需要一個單位時間的運算。（25 分）
(二)設計一個副程式 sift(A, r, n)其輸入參數 A 是一個矩陣，n 是矩陣 A 的大小，1≦r≦n 是一個指標。副程式 sift(A, r, n)的功能是將 A[r]為樹根的子樹變成 heap。（在呼叫 sift(A, r, n)之前， A[i]的所有子樹必須已經是 heap）並分析其計算時間確實是 O(h(r))，其中 h(r)是以A[r]為樹根的子樹的高度。（10 分）
阿摩線上測驗
登入
。（也就是 e 不會在任一個 G的最小權重擴張樹中）（10 分）
。（15 分）