阿摩線上測驗
登入
首頁
>
研究所、轉學考(插大)◆資料結構與演算法
>
111年 - 111 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147272
> 申論題
7.(10分)Run the insertion sort on the following array: (14,10,3,8,6,4,13) step by step.
相關申論題
8.(10分)Give an asymptotic upper bound for \( \mathrm{T(n)} = 7\mathrm{T}\left(\lfloor \mathrm{n} / 3\rfloor \right) + \mathrm{n}^2 \) where \( \mathrm{T(n)} \) is constant for \( \mathfrak{n} < 3 \). Your upper bound should be as tight as possible.
#605660
1. Design a randomized algorithm to find the i-th smallest element in a given array of length \( n \). The expected running time of your algorithm should be \( O(n) \). (15分)
#605661
2. Run the Floyd-Warshall algorithm on the following graph to find the all-pairs shortest paths step by step. You should generate five matrices according to the Floyd-Warshall algorithm. (15分)
#605662
3. Run counting sort on the following array: (7,6,7,5,5,4,2,5,1,3,1,7,1,2,3) step by step. (10分)
#605663
4. Let us consider the recurrence \( T(n) = T(\lfloor n / 2 \rfloor) + T(\lceil n / 2 \rceil) + 1 \) for any positive integer \( n \). Use mathematical induction to show that \( T(n) \leq cn \) for some positive number \( c \). (10分)
#605664
(A)使用 merge sort 排序數列 69 5 85 36 12 20 59 4 73 31 17。並且說明每次處理數字時,所使用的條件和基準。(5分)
#605665
(B)使用 binary search 在排序好的數列尋找數字,比如31,並說明為何能達到 \( O(\log N) \) 的速度,N是數列的數字個數。(5分)
#605666
(A)將此 inorder statement: \( \mathrm{A} * \mathrm{B} + \mathrm{C} * (\mathrm{D} - \mathrm{E}) / (\mathrm{F} + \mathrm{H}) \) 轉為 postorder,並畫出它的二元樹。須按照以左到右讀取順序來做,以達到單一解答。(5分)
#605667
(B)設計一個算法使用 stack 來實現上述 inorder 轉 postorder,並且以上述 statement 說明如何使用 stack 來做轉換。(10分)
#605668
7. 使用 linked list 實作 stack,運用以下 C 語言程式:typedef struct node { int value; node *next;}void push (node **top, int new_value) { // assume top is not nullnode new_node = (node ) malloc (sizeof (node));// (A) 實作以下敘述 (5 分)// add new_node to stack by top}int pop (node **top) { // assume top is not nullint value;node deleting_node = top;// (B) 實作以下敘述(5 分)// remove the deleting node from stack, get the value of deleting nodefree(deleting_node);return value;}
#605669
相關試卷
115年 - 115 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147260
115年 · #147260
114年 - 114 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147250
114年 · #147250
113年 - 113 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147281
113年 · #147281
112年 - 112 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147280
112年 · #147280
111年 - 111 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147272
111年 · #147272
110年 - 110 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147276
110年 · #147276
110年 - [非官方正解]110 國立臺灣大學_碩士班招生考試_電信工程研究所丙組:資料結構與演算法(B)#113108
110年 · #113108
110年 - [非官方正解]110 國立中央大學_碩士班招生考試_資工類:資料結構與演算法#105890
110年 · #105890
109年 - 109 國立臺北大學_碩士班一般入學考試試題_資訊工程學系:資料結構與演算法#147273
109年 · #147273
109年 - 109 東吳大學_轉學生招生考試_資訊管理學系三年級︰資料結構#105850
109年 · #105850