113 師大資工所考古題詳解｜軟體考點分析

題型與配分

全卷 7 頁、13 題、100 分，作答於答案卷，卷面沒寫倒扣。卷面注意事項是「請依序在答案卷上作答，並標明題號，不必抄題」與「答案必須寫在指定作答區內，否則依規定扣分」。

逐題考點

• 第 1 題（5%）｜寫出程式的輸出：f1(int a) 在 a > 0 時先呼叫 f1(a/2)，再印出 a % 2，主程式呼叫 f1(12345)
• 第 2 題（5%）｜寫出程式的輸出：四個函式 f1 到 f4 放進 function pointer array int (*func[4])(int)，以 enum State（STATE_00 到 STATE_03）當狀態，輸入 array {1, 0, 0, 1, 1, 0, 0, 1, 1, 0}，從 STATE_00 開始依序呼叫 func[s](input[i])，最後印出 s
• 第 3 題（5%）｜給 f3(char *s) 的程式碼（用 while 迴圈逐字元 traverse 字串，迴圈內以條件運算式更新字元），描述這個函式的功能
• 第 4 題（5%）｜兩支程式分別宣告 char str[] = "Hello Kitty" 與 char *str = "Hello Kitty"，再各改一個字元為 'W'。題目說明前者輸出 Hello Witty、後者輸出 Segmentation Fault，要求說明後者失敗的原因
• 第 5 題（5%）｜gets() 從標準輸入讀一行到 s 指向的緩衝區，直到換行或 EOF，並說明這個函式已被棄用，要求解釋為什麼不應該使用
• 第 6 題（5%）｜給 macro OFF(TYPE, MEMBER) 與 TEST(ptr, type, member)，描述 TEST 的用途
• 第 7 題（10%）｜圍棋的氣（liberty）：與棋子在上下左右直接相鄰的空點，或透過同色棋子連成的一串連到這種空點。要求寫出 int count(int board[19][19], int x, int y)，計算指定位置的棋子或棋串的氣數；board 為 19×19，0 是空點、1 是黑子、2 是白子，可以假設給定的位置是黑子
• 第 8 題（7%）｜(a) 2% n 個節點的 binary tree，求高度的最壞時間複雜度，要給合理的說明 (b) 2% n 個節點的 binary tree 最多有幾個葉節點，要給合理的說明 (c) 3% 判斷兩棵 binary tree（結構與節點資料都相同）是否相等的 equal(first, second)，填完三個空格
• 第 9 題（7%）｜給圖 G1 的 adjacency list：(a) 4% 畫出從頂點 2 出發的 DFS 與 BFS spanning tree (b) 3% 畫出 biconnected component
• 第 10 題（5%）｜給一棵 AVL tree（節點 50、30、42、48 等），依序插入 40、10、20、32，畫出每次插入後的四棵 AVL tree
• 第 11 題（5%）｜用 singly linked list 實作 queue，front 與 rear 分別指向兩端，空 queue 時兩者皆為 null，補完 addq 與 deleteq 的五個空格
• 第 12 題（6%）｜以 Dijkstra 演算法求從頂點 v 到其他各頂點的 shortest path 成本，邊成本存在 adjacency matrix 中，且為非負整數，補完 choose() 與 shortest_path() 的四個空格
• 第 13 題（30%）｜bipartite graph 與 maximum matching：
• 第 13(a) 題（5%）｜給 adjacency list（頂點 a 到 f），從頂點 a 開始做 DFS，鄰居依字母順序處理
• 第 13(b) 題（5%）｜(a) 的圖是否為 bipartite graph，是的話寫出頂點的分割
• 第 13(c) 題（5%）｜提出用 DFS 檢查一張圖是否為 bipartite graph 的演算法
• 第 13(d) 題（10%）｜給一個有源點 s、匯點 t 的網路，用 Ford-Fulkerson 求 max flow 與 min cut，min cut 要寫出頂點的分割
• 第 13(e) 題（5%）｜說明 Ford-Fulkerson 方法如何用來解最大 bipartite matching 問題

作答時要注意的地方

1. 第 1–7 題共 40 分是 C 語言題，第 8–13 題共 60 分，其中第 8(c)、11、12 題也是 C 或 C++ 程式填空。
2. 第 4 題題目已說明兩支程式的輸出結果，問的是第二支為什麼失敗。
3. 第 7 題允許假設給定位置是黑子。
4. 第 8(a)(b) 要給合理的說明才有分。
5. 第 10 題要畫出每次插入後的四棵樹。
6. 第 13(a) 題鄰居依字母順序處理。

準備方向

• C 程式的填空、追蹤與手寫：113 第 1–4、6、7、8(c)、11、12 題；106 第 2(1)、3(1)、4(2)、5(1) 題、107 第 1(c)(d) 題、108 第 2 題、110 第 7、8 題、112 第 1、2、6 題、114 第一題也有。
• 複雜度分析：113 第 8(a)(b) 題；106 第 3(2)、5(2)、6(b) 題、107 第 7(a)(c) 題、108 第 4(a)(b) 題、109 第一(8)、四(c)、六(a)題、110 第 1、2 題、111 第 4、5 題、112 第 1(b)、8(a) 題、114 第三、五題、115 第 1、5、6 題也有。
• binary tree 與 BST：113 第 8、10 題；107 第 3(a) 題、108 第 1.1、1.8、1.10、1.12 題、109 第一(2)、一(7)、二題、110 第 2(a)、3-5、8 題、111 第 1 題、112 第 3 題、114 第三(二)(四)題、115 第 5 題也有。
• 圖的表示法：113 第 9 題；108 第 1.3 題、109 第一(3)題、110 第 3-1、3-2 題、112 第 6(a) 題、114 第三(一)、四題也有。
• 圖的 traversal 與 connectivity（DFS／BFS、dfn／low、biconnected、strongly connected）：113 第 9、13(a) 題；106 第 4(1) 題、107 第 2(b) 題、108 第 1.3、1.5、3、5(a) 題、110 第 6 題、111 第 3 題、112 第 6 題、114 第四題、115 第 8 題也有。
• Linked list、stack 與 queue 的實作：113 第 11 題；106 第 2(1) 題、108 第 1.9、2(a) 題、109 第四題、110 第 7 題、112 第 2 題、114 第一題也有。
• shortest path：113 第 12 題；106 第 4(2)、8 題、107 第 4、6 題、110 第 10、11 題、111 第 7 題、114 第七(二)題、115 第 9 題也有。
• max flow 與 bipartite matching：113 第 13 題；109 第八題也有。