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

(a)What are the time complexity and space complexity using an iterative algorithm? (5%)

(b)What is the space complexity using a recursive algorithm? (5%)

(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(n² ) > O(n log n) (2%)

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

(c) O(2ⁿ ) > O(n² ) (2%)

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

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

3. Graph traversal can be either depth first traversal or breadth first traversal. Please
write 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, in
DLlist. Draw a figure to show this insertion. Note that you should label the
affected fields so that you show how each step in the insertion function is
executed (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 a
node 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 less
than k. Therefore, the record with key k can be placed in position count[k] of an
output list. (You should beware of the possibility of equal key values. See an
example in Figure 1.) Assume that all keys of the records are integers and their
values are in range of [0, d], where d is a constant. Write an algorithm to sort a set
of records with size n by the key value using this method (including how to
determine the count[k]). (15%)