阿摩線上測驗
登入
首頁
>
公職◆資料結構
> 107年 - 107 地特三等 資料結構#73482
107年 - 107 地特三等 資料結構#73482
科目：
公職◆資料結構 |
年份：
107年 |
選擇題數：
0 |
申論題數：
11
試卷資訊
所屬科目：
公職◆資料結構
選擇題 (0)
申論題 (11)
⑴請證明：輸入任意兩個正整數，此程式執行一定時間後就會停止，不 會造成無窮迴圈。
⑵假設 a ＞ b，請證明此程式之 while 迴圈（第 3 行）至多只會被執行 2 log2 b +1 次。
⑴假設每個邊的權重都不相同。請證明由 L 中這些邊所構成的子圖（edge induced subgraph）G[L]沒有迴圈。
⑵G[L]是否一定是 G 的擴張樹（spanning tree）？若是請證明之，若不 一定是請給一個反例。
⑶用以上之結論，設計一個計算 G 的最小權重擴張樹（minimum spanning tree）的演算法。
⑷在一般的應用中，邊的權重可能會相同，請修正上述之演算法，使修 正後之演算法可以正確找出答案。
⑴已知所有的正整數 x
i
≤ M。請設計一個 O(n + M )時間的演算法將這些 整數由小到大排列。
⑵已知所有的正整數 xi ≤ n
2
。請設計一個 O(n)時間的演算法將這些整數 由小到大排列，或證明這是不可行的。
⑴用 sift(A, r, n)設計一個線性時間的演算法，將陣列 A[1..n]變成 heap。
⑵分析以上所設計演算法的計算複雜度為 O(n)。
五、斐波納契數（Fibonacci number）Fn的定義是F
0
= 0, F
1
= 1, F
n
= F
n－1
+ F
n－2
, n＞ 1。 計算 Fibonacci number Fn的演算法，以類似 C 語言表示如下：
其中資料型態 integer 表示整數。假設輸入的整數 n＞1。主程式執行 Fib(n)，則副程式 F(n)第 4 行之指令：
f [n]= F(n－1)+ F(n－2)會被執行幾次？請說明理由。（20 分）
阿摩線上測驗
登入
阿摩線上測驗
登入
