資訊處理 114 年程式語言考古題

請詳述下列四種排序（sort）演算法的運作原理及其時間複雜度。（25 分） ㈠泡沫排序（bubble sort） ㈡插入排序（insertion sort） ㈢合併排序（merge sort） ㈣快速排序（quick sort）

二元樹（binary tree）是一種常見的資料結構。對二元樹的任一節點（node） 而言，其可能包含的子節點（children）數量為0、1 或2。舉例來說，對 於一個具有3 個節點的二元樹，其可能的結構有以下5 種： ㈠請使用遞迴（recursion）的方式撰寫一個C 語言函數int nTrees(int n)來 計算具有n 個節點的二元樹，共有多少種不同的二元樹結構。（20 分） ㈡在許多情況下，使用遞迴的方式所撰寫的程式不是最有效率的方法。 請問可以使用何種程式撰寫的方法來提高㈠的程式的執行效率？（5 分）

若我們使用C 程式語言，定義了如下的結構（struct） typedef struct { char frst_name[20], last_name[20]; int score; char grade; } student_t; 並宣告兩個變數為此結構 student_t stu1, stu2; 請分別判斷下列8 個敘述是否有可能為有效（valid）的敘述或是一定為 無效(invalid)的敘述，並詳述其理由。（25 分） student_t A_list[30]; printf("%s", stu2); printf("%d %c", stu2.score, stu2.grade); stu1 = stu2; if (stu1.grade == stu2.grade) printf("Same Grade"); if (stu1 == stu2) printf("Same Structure"); stu1.last_name = "Donald"; student_func(&stu1);

請問下列C 語言程式執行後的輸出為何？（15 分） #include <stdio.h> int main(void) { int x = 0; do { switch (x) { case 0: printf("%d\n", x); case 1: x++; break; case 2: printf("3\n"); case 3: printf("%d\n", x * 3); case 4: x += 3; break; default: x = x * 2; printf("%d\n", x / 3); } } while(x < 10); return (0); }

請描述何謂白箱測試（white-box testing）和黑箱測試（black-box testing）。 （10 分）