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

1. Here is the array of 10 integers:(20%)
5 3 8 9 1 7 0 2 6 4.
We will sort the integers from smallest to largest. Please draw this array after the FIRST iteration of the large loop using (a) insertion sort; (b) selection sort.

2. Insert the keys 8, 6, 3, 2, 7, 5 into an empty binary search tree in this order. Please answer (a) preorder traversal, (b) postorder traversal and (c) breadth-first traversal of the binary search tree.(20%)

3. (a) How many nodes are in a graph with n edges? (b) Please prove it.(10%)

4. 請將以下的時間複雜度，由小至大排列 (20%) \( O(n^3) \), \( O(n!) \), \( O(1) \), \( O(n^2) \), \( O(n \log n) \), \( O(2^n) \), \( O(n^n) \), \( O(n) \), \( O(\log n) \)

5. 一個以行為主(Column major order)的陣列A，每份資料占1 個記憶單位，第一個元素A［0, 0］位址為2100，A［4, 5］位址為2196，則A［6, 4］的位址為何？(10%)

6. 請使用Kruskal’s algorithm找出下圖的最小生成樹。請寫出個步驟的變化與最後完成的最小生成樹(20%)