# 2018q1 第 4 週測驗題 --- ### 測驗 `1` ![](https://i.imgur.com/iqFZJkY.png) 分析以下程式碼,推敲 `FuncA`, `FuncB`, `FuncC` 的作用,並且推測程式執行結果。 假設條件: * `malloc` 總是成功而且返回的記憶體空間可讀寫 ```Clike #include <stdlib.h> #include <stdio.h> struct node { int data; struct node *next, *prev; }; void FuncA(struct node **start, int value) { if (!*start) { struct node *new_node = malloc(sizeof(struct node)); new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } struct node *last = (*start)->prev; struct node *new_node = malloc(sizeof(struct node)); new_node->data = value; new_node->next = *start; (*start)->prev = new_node; new_node->prev = last; last->next = new_node; } void FuncB(struct node **start, int value) { struct node *last = (*start)->prev; struct node *new_node = malloc(sizeof(struct node)); new_node->data = value; new_node->next = *start; new_node->prev = last; last->next = (*start)->prev = new_node; *start = new_node; } void FuncC(struct node **start, int value1, int value2) { struct node *new_node = malloc(sizeof(struct node)); new_node->data = value1; struct node *temp = *start; while (temp->data != value2) temp = temp->next; struct node *next = temp->next; temp->next = new_node; new_node->prev = temp; new_node->next = next; next->prev = new_node; } void display(struct node *start) { struct node *temp = start; printf("Traversal in forward direction \n"); for (; temp->next != start; temp = temp->next) printf("%d ", temp->data); printf("%d ", temp->data); printf("\nTraversal in reverse direction \n"); struct node *last = start->prev; for (temp = last; temp->prev != last; temp = temp->prev) printf("%d ", temp->data); printf("%d ", temp->data); printf("\n"); } int main() { struct node *start = NULL; FuncA(&start, 51); FuncB(&start, 48); FuncA(&start, 72); FuncA(&start, 86); FuncC(&start, 63, 51); display(start); return 0; } ``` ==作答區== `FuncA` 的作用是 * `(a)` 偵測輸入是否為 circular linked list,若是則將現有所有節點內容排序,否則不做事 * `(b)` 建立兩個節點並且安插在結尾,內容都是 `value` * `(c)` 尋找所有節點,當遇到符合給定數值 `value` 的節點時,將 circular linked list 的開頭和剛找到的節點串接 * `(d)` 建立新節點,內容是 `value`,並安插在開頭 * `(e)` 建立新節點,內容是 `value`,並安插在結尾 * `(f)` 建立兩個節點並且安插在開頭,內容都是 `value` * `(g)` `FuncB` 的作用是 * `(a)` 偵測輸入是否為 circular linked list,若是則將現有所有節點內容排序,否則不做事 * `(b)` 建立兩個節點並且安插在結尾,內容都是 `value` * `(c)` 尋找所有節點,當遇到符合給定數值 `value` 的節點時,將 circular linked list 的開頭和剛找到的節點串接 * `(d)` 建立新節點,內容是 `value`,並安插在開頭 * `(e)` 建立新節點,內容是 `value`,並安插在結尾 * `(f)` 建立兩個節點並且安插在開頭,內容都是 `value` `FuncC` 的作用是 * `(a)` 偵測輸入是否為 circular linked list,若是則將現有所有節點內容排序,否則不做事 * `(b)` 建立兩個節點並且安插在結尾,內容分別是 `value1` 和 `value2` * `(c)` 建立兩個節點並且安插在開頭,內容分別是 `value1` 和 `value2` * `(d)` 找到節點內容為 `value2` 的節點,並在之前插入新節點,內容為 `value1` * `(e)` 找到節點內容為 `value2` 的節點,並在之後插入新節點,內容為 `value1` * `(f)` 找到節點內容為 `value1` 的節點,並在之前插入新節點,內容為 `value2` * `(g)` 找到節點內容為 `value1` 的節點,並在之後插入新節點,內容為 `value2` * `(h)` 尋找所有節點,當遇到符合給定數值 `value1` 和 `value2` 的兩個節點時,將這兩個找到的節點相互串接 在程式輸出中,訊息 `Traversal in forward direction` 後依序印出哪幾個數字呢? Z1 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z2 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z3 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z4 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z5 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 在程式輸出中,訊息 `Traversal in reverse direction` 後依序印出哪幾個數字呢? Z6 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z7 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z8 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z9 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 Z10 = ? * `(a)` 63 * `(b)` 86 * `(c)` 51 * `(d)` 48 * `(e)` 72 * `(f)` 這個程式有缺陷,無法正確輸出數字 :::info 延伸題目: * 在上述 doubly-linked list 實作氣泡排序和合併排序,並提出需要額外實作哪些函示才足以達成目標 * 引入統計模型,隨機新增和刪除節點,然後評估上述合併排序程式的時間複雜度和效能分佈 (需要製圖和數學分析) ::: --- ### 測驗 `2` ![](https://i.imgur.com/KKSlhnO.png) 考慮以下程式碼,推敲程式作用並分析輸出。 假設條件: * `malloc` 總是成功而且返回的記憶體空間可讀寫 * `malloc()` 得到的地址成嚴格單調遞增函數 ```Clike #include <stdio.h> #include <stdlib.h> /* Link list node */ struct node { int data; struct node *next; }; int FuncX(struct node *head, int *data) { struct node *node; for (node = head->next; node && node != head; node = node->next) data++; return node - head; } struct node *node_new(int data) { struct node *temp = malloc(sizeof(struct node)); temp->data = data; temp->next = NULL; return temp; } int main() { int count = 0; struct node *head = node_new(0); head->next = node_new(1); head->next->next = node_new(2); head->next->next->next = node_new(3); head->next->next->next->next = node_new(4); printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); head->next->next->next->next = head; printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); head->next->next->next->next->next = head->next; printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); head->next = head->next->next->next->next->next->next->next->next; printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); printf("K5 >> %d\n", head->next->data); printf("count >> %d\n", count); return 0; } ``` ==作答區== `FuncX` 的作用是 (涵蓋程式執行行為的正確描述最多者) * `(a)` 走訪 circular linked list 所有節點,計算節點數量並更新 * `(b)` 走訪 circular linked list 所有節點,計算節點數量並更新,回傳最後一個節點和開頭的地址距離 (offset) * `(c)` 走訪 circular linked list 所有節點,回傳最後一個節點和開頭的地址距離 (offset) * `(d)` 判斷是否為 circular linked list,若為 circular 則回傳非零值,其他回傳 `0` * `(e)` 判斷是否為 circular linked list,若為 circular 則回傳 `0`,其他非零值 * `(f)` 判斷是否為 circular linked list,若為 circular 則回傳 `0`,其他非零值,過程中計算走訪的節點總數 * `(g)` 判斷是否為 circular linked list,若為 circular 則回傳非零值,其他回傳 `0`,過程中計算走訪的節點總數 `K1 >>` 後面接的輸出為何 * `(a)` No * `(b)` Yes `K2 >>` 後面接的輸出為何 * `(a)` No * `(b)` Yes `K3 >>` 後面接的輸出為何 * `(a)` No * `(b)` Yes `K4 >>` 後面接的輸出為何 * `(a)` No * `(b)` Yes `K5 >>` 後面接的輸出為何 * `(a)` 5 * `(b)` 4 * `(c)` 3 * `(d)` 2 * `(e)` 1 * `(f)` 0 `count >>` 後面接的輸出為何 * `(a)` 5 * `(b)` 4 * `(c)` 3 * `(d)` 2 * `(e)` 1 * `(f)` 0 ---