(1) [10 points] Please find the vertex sequence derived by DFS and BFS respectively. Note that we assume that node A is the root.

(2) [10 points] Please apply Kruskal's algorithm to drive the minimum cost spanning tree. Note that you must show your actions step by step.

(1) [5 points] Draw the corresponding binary tree T.

(2) [5 points] Is T a max heap? Is T a min heap? Explain your reasons.

(3) [15 points] Perform the following three heap operations sequentially: INSERT (18), INSERT (27) , DELETE on T. Draw the resultant tree after each operation.

(a) [5 points] Given an unsorted integer array of size n, does the binary search algorithm outperform the sequential search algorithm? Use the big-O notation to justify your answer.

(b) [5 points] Given an integer array A of size n, the following pseudo-code shows the quick-sort algorithm. Note that we assume that all array elements in A are distinct and the function medi um(2) will return the value x in A such that the number of integers that are larger than x is equal to the number of integers that are smaller than x. Besides, we assume that the running time of the function medi um(A) is O(r). Derive the worst case running time of quicksort (A) in terms of big-0 notation. (Note that you will get O points if you just give the answer directly.)

(c) [5 points] The following enhanced _quicksort algorithm witten in a C-like pseudo-code tries to first split the array A into three partitions and then recursively sorts the arrays s, M, and L. Note that we carefully design two selection functions, first selection function(A)and second selection function (A), to guarantee that min (A) ＜ x ＜y ＜max (A), where min (A) and max (A) denote the minimum element and the maximum element in array A, respectively. Moreover, we assume that the running time of each selection functions is O(n). Please tell us whether the enhanced quicksort algorithm is more efficient than the quicksort algorithm? Use the big-O notation to justify your answer.

(1) [5 points] Please convert the infix expression shown below into postfix form. Ax(B/(C-D)+E)xxF-G

(2) [10 points] Tell us the results of preorder and postorder traversals for the following binary tree.

(d) [5 points] Let n be the radius of a circle C and A(n) be the area of C. Let T2(n)=|sinθ|xlog A(n)= O(f(n) . Derive the function f(n).

110年 - 110 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#104251

109年 - 109 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#106105

107年 - 107 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#110049

106年 - 106 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#110221

102年 - 102 國立中山大學_碩士班招生考試_電機系(丙組)：資料結構#110205