115年 - 115 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#143912

一、 搜尋法比較 (10 分)
請比較線性搜尋(Linear Search)與二元搜尋(Binary Search)
：
(a)使用條件 (b)時間複雜度。

二、 遞迴與時間複雜度 (10 分)
請推導下列此遞迴函式印出次數的遞迴關係式並改出其時間
複雜度(以 Big-O 表示)：
int F(int n){
if(n<=1){
printf("X\n");
return 1;
}
printf("X\n");
return F(n-1) + F(n-2);
}

三、 Heap 與 Priority Queue：操作設計與複雜度 (20 分)
請回答：
(a) 何謂「最大堆(max-heap) 」？請寫出其結構性質與序性質。
(b) 用最大堆實作 Priority Queue 時，insert(x) 與 deleteMax() 的
主要步驟為何？
(c) 分析上述兩個操作的時間複雜度，並說明原因。

四、 中序運算式轉後序 (10 分)
將中序式：
(A − B) ∗ (C + D)/E
轉為後序(postfix)，請寫出結果，並簡述你使用堆疊法的關鍵規則(運算子優先順序與括號處理) 。

(a) Draw the tree after performing union(a, b) using Union function
with weighting rule. (10%)

(b) Draw the tree after performing find(b) on the tree rooted at b using Find function with collapsing rule. (10%)

(a) Fill in the contents of the hash table after inserting 701, 74, 9, 16,
708. Your answer should be in the form: (10%)

(b) Explain why the table size is better to be a prime number. (10%)

七、 Use the following graph for topological ordering. When there are multiple nodes can be selected for the next step, choose the node with the smallest number. Use DFS method. (10%)