103年 - 103 國立嘉義大學_碩士班(乙組)招生考試試題_資訊管理學系：資料結構#146025

科目：研究所、轉學考(插大)-資料結構 | 年份：103年 | 選擇題數：0 | 申論題數：17

試卷資訊

所屬科目：研究所、轉學考(插大)-資料結構

選擇題 (0)

申論題 (17)

1. 右側程式碼是一個排序函式，n 個待排序資料存放於 Array a(從 a[1]放起)：
(1) 請依照程式分析時間/空間複雜度？按上述分析與實作方式，您認為它適合什麼情況(條件)下的排序？(10 分)
(2) 為了實測 mySort()函式對一個有20 筆資料的 list 的排序效率，因此以右側程式碼進行測量。但是執行結果duration 都是 0 秒。為什麼會這樣？(5 分)
(3) 承(2)，請提出兩個改良辦法。(5 分)
2. 針對以下各小題的問題與描述，請詳細提出您的分析與見解。(20 分)
(1) List sort 或 Table sort 本身並不是真正的「排序」演算法，所以他們的作用是？為什麼需要？
(2) Array 資料結構適合用來實作 Stack，但不適合 FIFO queue。
(3)造成記憶體發生 Dangling problem 的原因。
(4)利用 k-way merging 來進行 External sorting 時，理論上 k 越大、整體效能越高，但實際上不是。
3. 為了計算出某個 Weighted graph 的 Minimal cost spanning tree，有許多演算法可以採用，例如 Kruskal’s algorithm、Prim’s algorithm、或 是 Sollin’ s algorithm 等 。 前 述 三 個 演 算 法 都 屬 於 Greedy-methodalgorithm 類型。
(1) 請以前述任一演算法為例解釋什麼叫 Greedy-method algorithm？但不是所有的問題都可用 Greedy-method 的解法，因為它有什麼可能的缺點？(8分)
(2) 上 述 這 些 方 法 皆 會 重 複 一 樣 的 動 作 ， 因 此 可 以 採 用 Recursive 或Iterative 的模式來予以實作。雖然，理論上，兩種模式的時間複雜度都一樣，但實際執行時，前者會慢於後者，為什麼？(7 分)
4. 右圖是以 AOE network 畫出來的某專案進度規劃圖。回答以下問題：
(1)本專案最短可以在幾天內完成？(5 分)
(2) a6 所需的工作天數為 0，請問這有什麼作用？(5 分)
(3)請問在(1)的執行期限下，如果 a0 一開始就因故延遲了一天完成，請問專案經理應該緊盯那些工作？以確保他們在 ready 時會即刻開工，進而保證專案可以準時完工。(5 分)
5. (1) 請 以 「 Binary search tree 」 與 「 Unordered array 的 Sequential...start = time(NULL);mySort(list, 20);stop = time(NULL);duration = difftime(stop, start);...void mySort(element a[], int n) {int i, j;for( j = 2; j <= n; j++) {a[0] = a[j];i = j-1;while( a[0].key < a[i].key ) {a[i+1] = a[i];i--;}a[i+1] = a[0];}}V 4a5=12a2=5a1=5a0=4 fi nishst artV 1V ０V 2V 3a3=2 a4=3 V 5a6=0 a7=2
search」為基礎，比較 Static hashing 的搜尋機制有何優缺點？(5 分)
(2) 針對上述搜尋法所需的 Hash function 的設計上，首要注意的特質是「盡量減少 Collision 的發生，並在 Collision 發生時，採用有效的 Overflow應變機制」。請詳細說明引號內的句子是什麼意思。(5 分)
6. 以下的 Array A 用以表示一個 Complete binary tree，請回答下列小題。i 1 2 3 4 5 6 7 8A[i]29 23 22 17 12 5 11 14
(1) 請先畫出對應的 Tree，再詳細分析解釋這是一個 Max heap 或是 Minheap？(5 分)
(2) 我們可以利用 Heap 的特質來做排序，請把 A 當作未排序前的 Input，完成由大到小的排序。(請以 Heap tree 的格式，將排序每階段的過程畫出) (10 分)
(3) 類 似 概 念 亦 可 使 用 Selection tree 的 概 念 來 排 序 ， 例 如 ， 將 A 所 有Elements 當作 Leaf nodes，透過 Winner tree 依序產生最大值、並Output 之。請分析這個方法與(2)的方法在效能上的差異。(5 分)