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

科目：中山◆電機◆資料結構 | 年份：102年 | 選擇題數：0 | 申論題數：15

試卷資訊

所屬科目：中山◆電機◆資料結構

選擇題 (0)

申論題 (15)

(a) [5 points] Given the size n of the input data, where n is a positive integer, we assume that the running time of a program is O(f(n). State the formal definition of O(f(n)).

(b) [5 points] Let 62f4b9484b59f.jpg. Tell us the value of62f4b975582d6.jpg Note that you will et o points if you just povide the ansver. In other words, you must show your reasons. 
(c) [5 points] Given the size n of the input data, where n is a positive integer, we assume that a program requires the running time T1(n) = O( f(n). Derive the function f(n) .

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

2. [5 points] Consider the following function F written in a C-like pseudo-code, which takes an array A of n positive integers and an initially-empty stack S as input parameters:
  62f4b9e0f0c34.jpg
What is the output (returned value) of the function F for the array A= [2, 14, 4, 7, 11, 18, 10, 15, 6, 23, 12, 8]?
(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.)
62f4bb2eb6478.jpg

(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.
62f4bd059bd7f.jpg
(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.62f4bdaa52327.jpg