(b) Delete 3 from the binary min heap shown on the right-hand side below.

2. What are the time complexities of the following functions, namely p1( ) ~ p4( )? No explanation is required. (20%) void p1(int n) { for(int i=0; i < n; i++) { for(int j=0; j < n; j++) { for(int k=0; k < n; k++) { for(int m=0; m < n; m++) { printf("!"); } } } } } void p2(int n) { for(int i=0; i < n; i++) { for(int j=0; j < 10; j++) { for(int k=0; k < n; k++) { for(int m=0; m < 10; m++) { printf("!"); } } } } } int p3(int n) { if (n < 10) { printf("!"); return n; } else { return p3(n-1) + p3(n-1); } } int p4(int n) { if (n < 10) { printf("!"); return n+5; } else { return p4(n-1) + 2; } }

3. When we use Kruskal's algorithm to solve the minimum spanning tree problem, an edge is added if it does not create a cycle. We use disjoint sets data structure to determine whether two vertices below to a same set. In disjoint sets, the uptrees are used to represent sets in the union-find algorithm. And, uptrees can be stored in two n-element arrays, where n is the number of items. The up array stores the parent of each node. The weight array stores the number of items in a set if the node is the root of a set. The weight array is ignored in this problem. (20%) 1 2 3 4 5 6 7 8 9 up 6 6 -1 3 8 -1 6 3 -1 weight (a) Draw the uptrees represented by the data in the up array in the above table.

(b) Draw the uptrees after performing union(find(2), find(8)) on the above data.

4. What is a binary search tree? Explain the reasons that a binary search tree should be balanced with respect to the heights of subtrees. (20%)

5. A list of n integers may contain duplicate elements of the same value. Give a method that can find all duplicate elements faster than O(n2). Explain your answer. (20%)

6. Explain the reasons that quick sort cannot efficiently sort massive amounts of data that do not fit into available main memory. Describe an external sort algorithm that can efficiently sort data in the slower external memory. (10%)

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

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

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

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

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

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

110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844

110年 - [非官方正解]110 國立高雄科技大學_碩士班招生考試_電腦與通訊工程系：資料結構(乙組)#110488

110年 - 110 國立高雄科技大學_碩士班招生考試_資訊工程系：資料結構#110422

110年 - 110 國立中山大學_碩士暨碩士專班招生考試_資管系/乙組:資料結構#105545