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

(a) Insert 6 to the binary min heap shown on the left-hand side below.

(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%)

(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(n²). 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%)