113 師大資工所軟體考點分析

題型與配分

科目「軟體基礎」，適用系所：資訊工程學系，全卷 7 頁、13 題、100 分。

逐題考點

C 語言部分（1–7，共 45%）

• 第 1 題（5%）｜遞迴函式 f1(12345)：先遞迴 f1(a/2) 再印 a % 2 —— 這是把 12345 轉成二進位輸出
• 第 2 題（5%）｜函式指標陣列 int (*func[4])(int) 搭配 enum 狀態，跑 10 個輸入後的最終狀態。這是有限狀態機
• 第 3 題（5%）｜描述 f3(char *s) 的功能（把大寫字母轉成小寫）
• 第 4 題（5%）｜char str[] = "Hello Kitty" 可以修改，但 char *str = "Hello Kitty" 修改會 Segmentation Fault，要說明原因（字串常數存放在唯讀區段）
• 第 5 題（5%）｜為什麼 gets() 絕對不該使用（無法限制讀入長度，必然存在緩衝區溢位風險）
• 第 6 題（5%）｜描述巨集 TEST(ptr, type, member) 的用途 —— 這是 Linux kernel 的 container_of，由成員指標回推所屬結構的起始位址
• 第 7 題（10%）｜手寫 C 函式計算圍棋棋串的「氣」：給 19×19 棋盤（0 空、1 黑、2 白）與座標，算出該棋子或棋串的氣數。這是 flood fill／DFS 的實作題

資料結構與演算法部分（8–13，共 55%）

• 第 8 題（7%）｜(a) 2% 求 n 節點二元樹高度的最壞複雜度（O(n)，要說明理由） (b) 2% n 節點二元樹最多幾個葉節點（⌈n/2⌉） (c) 3% 判斷兩棵二元樹是否相等的遞迴函式填空
• 第 9 題（7%）｜給 adjacency list：(a) 4% 從頂點 2 出發的 DFS 與 BFS 生成樹 (b) 3% 畫出雙連通元件
• 第 10 題（5%）｜對給定的 AVL 樹依序插入 40, 10, 20, 32，要畫出每次插入後的四棵樹
• 第 11 題（5%）｜用單向串列（front／rear 兩端指標）實作 queue 的 addq 與 deleteq，填五個空格
• 第 12 題（6%）｜Dijkstra 的 C++ 程式填空四格（choose() 的比較與 shortest_path() 的鬆弛條件）
• 第 13 題（30%）｜二分圖與最大匹配，五小題：
• (a) 5%｜給 adjacency list，從 a 開始做 DFS（鄰居依字母序處理）
• (b) 5%｜這張圖是否為二分圖？若是，寫出頂點的分割
• (c) 5%｜設計用 DFS 判斷二分圖的演算法（兩色著色）
• (d) 10%｜給流網路，用 Ford-Fulkerson 求最大流與最小割，最小割要寫出頂點分割
• (e) 5%｜說明 Ford-Fulkerson 如何用來解最大二分匹配（加超級源點匯點、容量設 1）

這份考卷的難點

1. 第 13 題佔 30 分，是十年最大的單題，五小題從 DFS 一路走到二分匹配的網路流建模。
2. 第 7 題要在紙上寫出可運作的圍棋算氣函式，需要處理棋串的遞迴走訪與重複計算的避免（同一口氣不能算兩次）。
3. 第 6 題的 container_of 巨集是 Linux kernel 的技巧，沒看過很難現場推出來。
4. C 語言部分佔 45%，而且考的是實務細節（字串常數唯讀、gets 的安全問題、函式指標陣列），不是課本語法題。

準備建議

• 113 年是師大 C 語言比重最高的一年（45%），而且偏向實務與安全（緩衝區溢位、唯讀區段、函式指標），建議實際寫過 C
• Ford-Fulkerson 解二分匹配的建模（113 第 13(e) 題）在台大 106、交大 114 也都考過，是跨校必守
• 二元樹的最大葉節點數 ⌈n/2⌉、求樹高是 O(n) 這類「看似簡單但要說理由」的題目，師大特別愛考
• 師大的程式填空題（環狀串列、queue、Dijkstra、樹的相等判斷）都來自 Horowitz 課本，建議把課本的程式碼看熟