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

1. Find the minimum spanning tree (MST) of the following graph by applying the Prim’s algorithm with Node 3 as initial node. Show the order of node joining the MST and the weight of MST. (20%)

(a) Delete the maximum item. Show the detailed steps, and draw the heap. (10%)

(b) After (a), add 53 into the heap. Show the detailed steps, and draw the heap. (10%)

(a) The operation to add/delete an item. (2.5%)

(b) To random access item. (2.5%)

(c) Memory space to store items. (2.5%)

(d) The number of items is unpredictable. (2.5%)

4. Give the adjacency matrix as follows. What is the corresponding adjacency list. (10%)

(a) HeapSort has worst-case time complexity of O(n log(n)). (4%)

(b) HeapSort makes no more than O(n 2 ) pairwise comparisons. (4%)

(c) MergeSort has best-case time complexity of O(n). (4%)

(d) InsertionSort make no more than O(n log(n)) pairwise comparisons. (4%)

(e) SelectionSort is stable. (4%)

6. Draw the contents of the hash table in the boxes below given the following conditions: The size of the hash table is 12. Open addressing and double hashing is used to resolve collisions. The hash function used is H(k) = k mod 12. The second hash function is: H2(k) = 7 – (k mod 7). What values will be in the hash table after the following sequence of insertions? Draw the values in the boxes below, and show your work for partial credit. 33, 10, 9, 13, 12, 45, 26, 17. (20%)