93學年上學期資料結構期中考參考解答(總分110分，滿分100分).doc

93學年上學期 資料結構 期中考參考解答 (總分110分，滿分100分) 1. Please describe the five phases of program development process. (10%) (Hint: System life cycle in page 1) ANS: (課本1-1) 1. Requirement: 依據專案目的的規格書，獲得輸入和輸出的資訊 2. Analysis: 主要有兩種：由下而上與由上而下 3. Design: 設計者從程式所需要的資料物件和資料的運算兩方面來設計系統 4. Refinement and coding: 為每個資料物件選擇表示法，並撰寫他的各種運算之演算法 5. Verification: 以不同的資料測試程式，並改正錯誤 2. Please write down the output of the following program in C. (10%) #include stdio.h tower(int n, char a, char b, char c, char d){ switch(n) { case 0: break; case 1: printf(%c-%c\n, a, d); break; default: tower(n-2, a, c, d, b); tower(1, a, b, d, c); tower(1, a, b, c, d); tower(1, c, b, a, d); tower(n-2, b, c, a, d); } } main(){ tower(6,A,B,C,D); } ANS:共有21步 A-B; A-C; B-C; A-D; A-B; D-B; C-A; C-B; A-B; A-C; A-D; C-D; B-D; B-C; D-C;B-A; B-D; A-D; C-B; C-D; B-D; 3. Reordering the following complexity from smallest to largest: (5%) n log2 (n) n + n2 + n3 24 ANS: C D A B 4. Please fill the blank for the time complexity (both worst case and best case) of the following codes in the Θ notation, such as Θ(1), Θ(log n), Θ(n), Θ(n log n), Θ(n2), Θ(n3), Θ(2n), and so on. (20%) (a) Matrix addition. The matrix size is n by n. (4%) void add( int a[ ] [n], int b[ ] [n], int c[ ] [n]){ int i, j; for (i = 0; i n; i++) for (j= 0; j n; j++) c[i][j] = a[i][j] +b[i][j]; } Worst case: Θ(n2) . Best case: Θ(n2) . (b) Binary Search, “binsearch(list, searchnum, 0, n-1)” (4%) int binsearch(int list[], int searchnum, int left, int right) {// search list[0]= list[1]=...=list[n-1] for searchnum int middle; if (left= right){ middle= (left+ right)/2; switch(compare(list[middle], searchnum)){ case -1:return binsearch(list, searchnum, middle+1, right); case 0: return middle; case 1: return binsearch(list, searchnum, left, middle- 1); } } return -1; } Worst case: Θ(log n) . Best case: Θ(1) . (c) Sequential Search, “seqSearch(list, n,