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

1. 請將以下時間複雜度由低至高排列。(10 分)

\( O(n^3) \), \( O(1) \), \( O(n^2) \), \( O(n \log n) \), \( O(\log^2 n) \), \( O(2^n) \), \( O(n!) \), \( O(n^n) \), \( O(n) \), \( O(\log n) \), \( O(\log n^2) \)

2. 使用二元搜尋法，在{1,4,7,8,10,11,15}搜尋13是否在其中，搜尋的過程依序會與哪些數字比對？ (10分)

3. 使用以下程式，呼叫ABC(5, 2)函式後，總共會印出幾次 “abc”？ (10分)

4. 以Heap Sort排序十個數字42, 78, 12, 14, 96, 21, 7, 19, 36, 18的第一步是畫出Heap Tree，請畫出包 含十個數字的Heap Tree。 (20分)

5. 以下運算式為中序表示法(infix)，請分別列出其前序(prefix)及後序表示法(postfix)。 (20 分)

6. 請使用 Kruskal 演算法計算出下圖中最小成本生成樹(minimum cost spanning tree)的總成本數。 (10 分)

(a) Show the binary search tree S after each value is sequentially inserted into the binary search tree.

(b) Is the binary search tree S a full binary tree?

(c) Show the binary search tree S1 after inserting 18 into the above binary search tree S.

(d) Show the binary search tree S2 after deleting 7 from the binary search tree S1 by which we pick up the largest value in the left subtree.