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

(1) 請依照程式分析時間/空間複雜度？按上述分析與實作方式，您認為它適合什麼情況(條件)下的排序？(10 分)

(2) 為了實測 mySort()函式對一個有20 筆資料的 list 的排序效率，因此以右側程式碼進行測量。但是執行結果duration 都是 0 秒。為什麼會這樣？(5 分)

(2) 為了實測 mySort()函式對一個有20 筆資料的 list 的排序效率，因此以右側程式碼進行測量。但是執行結果duration 都是 0 秒。為什麼會這樣？(5 分)
(3) 承(2)，請提出兩個改良辦法。(5 分)

(1) List sort 或 Table sort 本身並不是真正的「排序」演算法，所以他們的作用是？為什麼需要？

(2) Array 資料結構適合用來實作 Stack，但不適合 FIFO queue。

(3)造成記憶體發生 Dangling problem 的原因。

(4)利用 k-way merging 來進行 External sorting 時，理論上 k 越大、整體效能越高，但實際上不是。

(1) 請以前述任一演算法為例解釋什麼叫 Greedy-method algorithm？但不是所有的問題都可用 Greedy-method 的解法，因為它有什麼可能的缺點？(8分)

(2) 上述這些方法皆會重複一樣的動作 ， 因此可以採用 Recursive 或Iterative 的模式來予以實作。雖然，理論上，兩種模式的時間複雜度都一樣，但實際執行時，前者會慢於後者，為什麼？(7 分)

(1)本專案最短可以在幾天內完成？(5 分)

(2) a₆ 所需的工作天數為 0，請問這有什麼作用？(5 分)

(1)本專案最短可以在幾天內完成？(5 分)
(3)請問在(1)的執行期限下，如果 a₀ 一開始就因故延遲了一天完成，請問專案經理應該緊盯那些工作？以確保他們在 ready 時會即刻開工，進而保證專案可以準時完工。(5 分)

(1) (1)請以「Binary search tree」與「Unordered array的Sequential search」為基礎，比較Static hashing的搜尋機制有何優缺點？(5分)

(2) 針對上述搜尋法所需的 Hash function 的設計上，首要注意的特質是「盡量減少 Collision 的發生，並在 Collision 發生時，採用有效的 Overflow應變機制」。請詳細說明引號內的句子是什麼意思。(5 分)

(1) 請先畫出對應的 Tree，再詳細分析解釋這是一個 Max heap 或是 Minheap？(5 分)

(2) 我們可以利用 Heap 的特質來做排序，請把 A 當作未排序前的 Input，完成由大到小的排序。(請以 Heap tree 的格式，將排序每階段的過程畫出) (10 分)

(2) 我們可以利用 Heap 的特質來做排序，請把 A 當作未排序前的 Input，完成由大到小的排序。(請以 Heap tree 的格式，將排序每階段的過程畫出) (10 分)
(3) 類似概念亦可使用 Selection tree 的概念來排序 ， 例如 ， 將 A 所 有Elements 當作 Leaf nodes，透過 Winner tree 依序產生最大值、並Output 之。請分析這個方法與(2)的方法在效能上的差異。(5 分)