(c)What is the time complexity using a recursive algorithm? (10%)
No explanation is required for (a) and (b). Show your work for (c).

(a) O(n2 ) > O(n log n) (2%)

(b)O(n!)>O(2n )(2%)

(c) O(2n ) > O(n2 ) (2%)

(d) O(n log n) > O(2n ) (2%)

(e) O(n log n) > O(n) (2%)

3. Graph traversal can be either depth first traversal or breadth first traversal. Pleasewrite pseudo code, without using recursion, for (a) depth first traversal (10%), and(b) breadth first traversal (10%).

(a) Assume that we want to add a new node between two nodes, anode and bnode, inDLlist. Draw a figure to show this insertion. Note that you should label theaffected fields so that you show how each step in the insertion function isexecuted (eg., newnode->llink, newnode->rlink, etc.). (10%)

(b)Write down the algorithms for the insertion and deletion functions in DLlist.Assume that you want to insert a new node to the right of anode and delete anode named dnode for a nonempty list. (15%)

5. Write the detailed steps of carrying out merge sort in the list (13, 4, 19, 38, 9, 27, 6,11, 25, 7, 20). (10%)

6. A simplest known sorting method called “counting sort” is described as follows.Declare an array count and set count[k] to the number of key values that are lessthan k. Therefore, the record with key k can be placed in position count[k] of anoutput list. (You should beware of the possibility of equal key values. See anexample in Figure 1.) Assume that all keys of the records are integers and theirvalues are in range of [0, d], where d is a constant. Write an algorithm to sort a setof records with size n by the key value using this method (including how todetermine the count[k]). (15%)

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

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

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

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

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

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

110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844

110年 - [非官方正解]110 國立高雄科技大學_碩士班招生考試_電腦與通訊工程系：資料結構(乙組)#110488

110年 - 110 國立高雄科技大學_碩士班招生考試_資訊工程系：資料結構#110422

110年 - 110 國立中山大學_碩士暨碩士專班招生考試_資管系/乙組:資料結構#105545