阿摩線上測驗
登入
首頁
>
中山◆電機◆資料結構
>
102年 - 102 國立中山大學_碩士班招生考試_電機系(丙組):資料結構#110205
> 申論題
題組內容
3.Consider the following weighted graph G(V,E) presented by the adjacency matrix.
(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.
相關申論題
(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)).
#471751
(b) [5 points] Let . Tell us the value of Note that you will et o points if you just povide the ansver. In other words, you must show your reasons.
#471752
(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) .
#471753
(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).
#471765
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: 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]?
#471754
(1) [10 points] Please find the vertex sequence derived by DFS and BFS respectively. Note that we assume that node A is the root.
#471755
(1) [5 points] Draw the corresponding binary tree T.
#471757
(2) [5 points] Is T a max heap? Is T a min heap? Explain your reasons.
#471758
(3) [15 points] Perform the following three heap operations sequentially: INSERT (18), INSERT (27) , DELETE on T. Draw the resultant tree after each operation.
#471759
(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.
#471760
相關試卷
110年 - 110 國立中山大學_碩士班招生考試_電機系(丙組):資料結構#104251
110年 · #104251
109年 - 109 國立中山大學_碩士班招生考試_電機系(丙組):資料結構#106105
109年 · #106105
107年 - 107 國立中山大學_碩士班招生考試_電機系(丙組):資料結構#110049
107年 · #110049
106年 - 106 國立中山大學_碩士班招生考試_電機系(丙組):資料結構#110221
106年 · #110221
102年 - 102 國立中山大學_碩士班招生考試_電機系(丙組):資料結構#110205
102年 · #110205