---
tags: 推甄, 中央資工
---

# 中央軟工 歷年考古題與推甄心得
今天剛放榜，看到中央一般組備取 128 名時，我的心涼了一半，但是軟工組卻正取，好爽。不枉費我花了一星期整理了這份筆記，這份筆記包含我能找到的歷屆考題，最後面還有我讀書時整理的筆記，希望能夠幫到也想報考中央軟工的學弟妹！

## 個人經歷
小弟我的成績和經歷也不是特別亮眼，就當作給各位想報中央軟工的人一個參考

* 國立臺灣海洋大學 資訊工程系
* 班排 29%，系排 23%
* 專題：AI 無人船
* 沒有比賽經歷，但有一些 side project

## 最終成績
### 一般組
* 資料審查：85.21
* 面試：81.07
* 結果：備取第 128 名 (悲)

### 軟工組
* 資料審查：89.34
* 筆試：76.00
* 結果：正取第 1 名 (喜)

這個結果我是真的沒想到，畢竟在寫程式題的時候我心理不是很有底，再加上我沒有照考卷規定圈題目和標註程式題使用的程式語言，超級怕他們給我扣分的。好在結果看起來他們沒有拘泥這個小細節 :D

總之，我很推薦程式還不錯，但系排成績不是很理想的人來考考軟工組，說不定這是你的翻身機會！

# 歷屆考古
## 115 年
### 觀念題
1. asynchronous 和 synchronous
* 說明兩者的差別
* 假如實作一個網路爬蟲，要怎麼使用非同步優化 (?
2. 測試
* 我們給一個購物網站寫了一個打折系統，問你要怎麼針對這個功能進行測試
* 黑箱與白箱測試是甚麼
* 如何對上述的系統進行黑箱與白箱測試
3. 要你探討 try catch
* 新手工程師寫出以下程式碼：

        try {
            AccessDatabase();
        } catch (Exception e) {
            raise Exception("Fail to access database.");
        }

* 資深工程師覺得這是脫褲子放屁，都要丟 exception 了幹嘛再用 try catch 包起來
* 題目要你從兩人的角度探討這段程式碼，並且如何權衡兩者的觀點
4. 要燒錄十個影片要用 multithread 還是 multiprocess；那回應 1000 個使用者對網頁的請求要用哪一個 (這題我跳過)
5. git 相關
* 考你知不知道 `git revert`
* 如何使用 git 找到修改某檔案的紀錄
6. 物件導向相關
* 給一段介面化的 Java 程式碼，問你使用介面有什麼好處的樣子
* 考你知不知道 OOP 三大要素：封裝、繼承、多型

### 程式題
1. 寫出 isSymmetric 函式，輸入一二元樹，判斷其有沒有對稱
2. 給一個資料庫表格
* 將資料庫進行正規化 (到 3NF 即可)
* 問你 SQL 與 NoSQL 差在哪
* 問這個系統適合使用 SQL 還是 NoSQL
3. 實作 2048 (這真的在搞)
4. 裸二分搜
5. 二維背包問題，我不會 :(
6. 給你一個數字 n，將其每一位數字取三方並加總成為新的 n，問你 n 有沒有辦法變成 153

## 114 年
[文章](https://www.dcard.tw/f/graduate_school/p/257185072)
### 觀念題
1. 平時如何對程式除錯
2. 前後端分離的優缺點
3. 對一個 Github repo 發送 Pull Request，描述過程中會進行的步驟、指令與作用
4. 製作一個可以讓顧客瀏覽書籍、下訂單的後端
* 說明什麼是 RESTful API，為什麼適合用於這樣的後端
* 顧客註冊帳號時 Email 衝突、找不到書籍、伺服器發生錯誤應該使用什麼 HTTP status code
5. 綜合題
* 解釋 API 與 SDK 的差別
* 解釋甚麼是 SQL 跟 NoSQL，差別在哪及適合的情境
* 解釋 hashing、encoding、encryption 及其用途
6. Git
* 公司有人誤刪 repo 重要內容，而且已經 commit 了，該如何處理
* 兩個團隊各自開了一個 feature branch，merge 的時候發現套件版本衝突，怎麼辦
* 功能上線才發現有問題，如何復原成原本的版本
7. 題目給定一段 C 程式，裡面分別用 macro 跟一般的函數實作 binary operation，請從執行速度、編譯速度面向解釋兩者的優缺點
8. C 程式指標操作
9. C 程式各種變數在記憶體中的位置 (heap, stack, uninitalized data segment, initialized data segment, text segment 其一)
10. 解釋 Docker 與 VM 的差別及使用情境
11. 找不到

### 程式題
1. Leetcode 917: Reverse Only Letters
2. Leetcode 239: Sliding Window Maximum, O(n + k)
3. 一英雄有四個技能四種傷害，問達到目標傷害的連記組合數 (可重複選)
4. 實作 Wordle
5. Merge 相鄰或重疊的 interval
6. Leetcode 16: 3Sum Closest
7. 給定一段 C# 或 java 判斷質數的函數，其中會 throw exception，題目要求對他寫 test case
8. 爬樓梯，一次可以爬一階或兩階，輸入總階數，輸出可能的爬法及數量

## 113 年
[文章](https://home.gamer.com.tw/creationDetail.php?sn=5823838)
### 觀念題
1. Restful API 的名詞和概念解釋
2. 你是槍戰遊戲公司的總監，由於封包的丟失，你們遊戲的延遲極高。請提出五種延遲的可能性與解決方案，讓團隊能在短時間內解決問題
3. 軟工測試
* 寫程式時如何測試
* 甚麼是黑箱、白箱測試
* Unit Testing 是甚麼
* End-to-end Testing 是甚麼
* Integration Testing 是甚麼
4. 設計醫院的資料庫系統，統籌醫生護士與病人 (細項不清楚)，需要畫出 UML 圖與 use case diagram
5. 給定一段物件導向程式碼，問他為啥寫的不好，可以怎麼改
6. 二分搜程式碼除錯
7. 多線程程式碼除錯
8. Git 相關問題

### 程式題
1. 寶可夢對決：物件導向設計
2. 給定村民人數 N 與確診村民編號 M，接下來給定哪對村民接觸過，求出要隔離的村民有哪些人
3. Leetcode 2390: Removing Stars From a String
4. Leetcode 1338: Reduce Array Size to The Half
5. 給定一個 Points list 與 Rectangle bound，求在範圍內的 Points 有哪些。O(logN) 有加分
6. 給定一角色體力與基礎攻擊力，求單一攻擊中能打出的最高傷害。同時也包含花費體力使用道具：
* 增加攻擊次數減少基礎傷害
* 增加攻擊傷害
> 本題暴力解不給分
7. Leetcode 189: Rotate Array

## 112 年
[文章](https://www.dcard.tw/f/graduate_school/p/240549194)
### 觀念題
1. 關聯式資料庫、物件導向程式設計、index 觀念
2. Call stack 的概念
3. 抽象化與介面的差別
4. 給定一資料庫設計案例，問哪裡可以改進
5. Debug 觀念
6. 給定一段 Java code，問繼承關係違反甚麼原理

### 程試題
1. 字串處理，輸入 `abc` 輸出 `defdefdef`
2. 給星星座標找距離，判斷這些星星的距離可以組成幾種星座 (考卷有給公式)
3. 寫出一段程式碼找出 Binary Tree 中子節點數值 <= root 的個數
4. 給定一 Sorted Array 找出重複的開始與結束點
5. 給定一串 Vector 判斷能不能湊成一個正方形
6. 火車由隧道左右往中間開，蒼蠅在隧道中間，看到火車時會往反方向飛，請問蒼蠅會死在哪

## 111 年
網站標題寫 2022，但從最後編輯時間推算上我覺得應該是 2021 的題目
但我懷疑我找錯，這些題目和歷屆考的東西差距太大了，不過就放在這裡做為參考
[文章](https://hackmd.io/@Quantami/2022CSIE_apply)
### 觀念題
1. 河內塔類題：3 個柱子、N 個圓盤
* 求 A 柱 3 個圓盤移動到 C 柱所需的流程
* 同上，改為 4 圓盤
* 求移動 N 個圓盤所需的次數通式
2. 披薩定理類題：小明與小華分一份披薩。在圓內隨機取一點切八塊、每塊 45 度的披薩，由順時針將每片披薩編號 1~8，而小明選奇數塊，小華選偶數塊，請問兩人拿到的披薩總量是否一樣多 (面積是否一樣)
* 證明 **披薩定理 N=4** 的狀況
* 我們真的學過嗎 (惱)
3. 給予多個關鍵字 (電腦圖學、資料庫、人工智慧...)，說明以下設計過程
* 一個手機端的虛擬輔導老師，需得以理解學生的情緒與對話，並給予指導與建議
* 真實的輔導老師可以在電腦端查看上述的紀錄，並給予建議
> 手機可以用 5G 連上網路、具有麥克風與鏡頭，但運算能力有限
4. AI Supremancy 論述：給予以下宣稱，說明你相信或不相信並探討可行性
* 由於深度學習、語音辨識技術的快速發展，現在電腦已經可以替代多數客服的工作
* 現在自駕車其實已經可以達到完全自駕的程度，只是法律上限制能不能完全上路的問題而已
* 史丹佛大學的數據庫經過長期累積所做出來的成果顯示：目前機器人回答問題集的準確率已經大約等於90%，代表現在機器人已經可以回答人類的大多數問題
* 現在機器人自動推薦的成果亮眼，在各大網路公司如Netflix, Amazon都已經使用機器人來自動推薦顧客商品...
5. 數學論述：說明高中的「機率」如何在資工系有所應用，請舉出實際例子
6. 綜合
* 給予已經猜 5 次的 1A2B 遊戲，數字不重複，說明接下來會如何猜及理由
1. 1470 -> 2B
2. 2589 -> 1B
3. 2386 -> 2B
4. 1509 -> 2B
5. 0381 -> 1A1B
* 你為何適合本科系

## 110 年
沒找到 :(

## 109 年
[文章](https://medium.com/@rozendhyan/%E4%B8%AD%E5%A4%AE%E8%BB%9F%E5%B7%A5%E6%8E%A8%E7%94%84%E5%BF%83%E5%BE%97-e7564687ebea)
### 觀念題
1. Debug 觀念
2. 測試觀念
3. Dirty code
4. 甚麼是 segmentation fault
5. 將費氏數列轉為 tail recursion
6. tree search (BFS)
7. 一家公司怎麼在客戶使用狀態下測試新功能

## 108 年
[文章](https://www.ptt.cc/bbs/graduate/M.1541334651.A.112.html)
### 觀念題
1. 闡述程式從原始碼到生成執行檔的過程
2. 使用一台安卓手機的 GPS 系統可能會會遇上什麼問題
3. 名詞解釋：單元測試、整合測試、系統測試
4. 如何解決 Memory leak
5. 全域變數 (?

### 程式題
1. 給定一 Linked List，刪除重複值的節點
2. 給定一串數字，要形成合法 IP 有哪些切法
* 255255113
* 255.255.1.13、255.255.11.3
3. 給定一個 Tree，找到最遠葉節點的最短路徑
4. 100 塊找零錢，有哪些找法
5. 給定兩個矩形座標，求兩矩形相交面積

### 英翻中
給一篇英文短文，要翻譯成中文，是有關 Computer Vision 的東西

# 重點整理
這裡是我整理的歷屆考古筆記，只能說有讀有機會

## 軟體工程

### Git
首先，請乖乖使用 Git Bash，刪掉 Github desktop (確信)
#### 重點
* `git reset`：把目前狀態設定為以前 commit 的版本，該版本之後的 commit 會消失
* `git revert`：把目前的版本推回以前 commit 的版本，並新增一個 commit，該版本之後的 commit 仍會存在
* `Pull Request` 流程：對別人的 repo 發 PR
1. Fork 別人的專案到自己的 Github 上
2. 對這個 repo 進行開發
3. 開發完之後於 Github 建立新的 **Pull Request**
4. 專案原作者審查後，決定是否採納

### 測試
* **單元測試**：針對 **模組** (軟體設計中的最小、可單獨執行的單位) 做正確性檢驗
* 由開發人員進行測試
* 單元測試架構：

* **整合測試**：將各個 **單元** 合併為更大的架構，測試組件間交互的正確性
* **單元整合測試**：檢查單元間整合的缺陷
* **系統整合測試**：測試外部系統與 API 的交互
* 多人或第三方人員執行

* **系統測試**：測試系統驗證其是否滿足需求，環境需與上線時一致
* 測試重點：功能性需求、系統的功能、非功能性需求

* **驗收測試**：確認系統是否符合設計規格及契約需求

* **端對端測試 E2E**：通常在系統測試階段使用的測試方法
* 關注「用戶使用流程」及「業務流程」
* 模擬用戶的完整行為，從頭到尾 (end-end)，確保軟體流程中所有的系統都能正確串接並運作

* **黑箱測試**：模擬使用者使用的方式進行測試
* 又稱功能測試，測試者不需要知道其中的運作邏輯，只要知道正確的輸入輸出即可
* 多用以測試邊界條件

* **白箱測試**：針對資料流及系統流程進行測試
* 資料流測試：確保資料在執行運算的過程中的正確性
* 系統流程測試：系統有對應的流程圖。測試過程中，測試必須包含所有的路徑，確保流程正確性

### Docker v.s. VM
Docker 屬於 **容器**，旨在將 **作業系統** 虛擬化，好讓其具有可攜性。而 VM 則是將 **硬體** 虛擬化

### 抽象化與介面
在軟體工程的角度下：
#### 抽象化
將複雜的東西隱藏起來，只給你看到 **你需要知道的**
我們以自動販賣機為例
* **內部細節**：裡面有齒輪、馬達、感應器、複雜的電路板、怎麼判斷你投了多少錢、怎麼檢查庫存... 這些東西，你根本不想知道，知道了也沒用。
* **如何抽象化**：將上面複雜的邏輯，全部塞進鐵皮箱子裡，給你投幣口與幾個按鈕進行操作
* 這樣，我們只要知道 `投錢 => 按按鈕 => 拿飲料` 即可

#### 介面
就是抽象化後，留給使用者的「投幣口與按鈕」

### 如何在用戶使用的情況下測試

#### 金絲雀發布
就跟礦工會帶金絲雀下礦一樣，如果金絲雀掛了，礦工也是時候該跑了
現在我們共使用 100 台伺服器，其中 99 台跑原本穩定的舊版本，只挑選一台跑新版本，並且只讓 1% 的流量存取該伺服器。
我們就盯著這一台伺服器，如果順利運行，慢慢增加新版本的伺服器數，直到跑道 100%，如果炸了，則將所有伺服器切回舊版。

#### 藍綠部署
藍色代表舊版本，綠色代表新版本。
在用戶使用服務的情況下，直接將 100% 的流量切換到 **綠色**，如果炸了就切回去 **藍色**

## 資料庫

### SQL v.s. NoSQL
| 特性 | SQL (關聯式) | NoSQL (非關聯式) |
|:-:|:-:|:-:|
| 資料模式 | **Table** 表格，結構固定 | 可有多種模型，結構自由 |
| Schema | **Predefined (事先定義)** Schema-on-write | **Dynamic (動態)** Schema-on-read |
| 一致性 | **ACID** 強一致性，保證資料絕對正確 | **BASE** 最終一致性，優先保證資料隨時可用 |
| 擴展方式 | **垂直擴展** 專注於將一台機器變得更強 | **水平擴展** 多加幾台伺服器一起工作 |
| 適合的情境 | 嚴謹、不能出錯的使用情境：金融；資料關係複雜，需要 join；資料結構固定 | 巨量資料；高併發讀寫；資料結構常變化 |

SQL 就像一個嚴謹的鑒，NoSQL 就像一個隨興的 homo（暴論）。

### 關聯式資料庫
大家最熟知的資料庫類型，如 MySQL
#### Schema
* 資料庫的 **設計圖**，需事先定義好 **table** 的樣子，**column** 有哪些、能放什麼 **資料型態**
* 需要先定義好 schema 才能放資料
* **主鍵 Primary Key**：一個 table 中，用來分別每一列的欄位，不能為空也不能重複
* **外部鍵 Foreign Key**：用來建立 table 與 table 之間關係的欄位

#### ACID 原則
關聯式資料庫保證每次 **交易** 絕對可靠的特性
經典的案例：銀行 A 要轉帳 114514 元給銀行 B
* **A-Atomicity (原子性)**：
* 要嘛做完，要嘛全都不要做
* 保證交易完成時， A 銀行 -114514，B 銀行 +114514 這兩個動作都順利完成

* **C-Consistency (一致性)**
* 交易前後，資料庫要是合法的狀態
* 例如 **帳戶的餘額不能是負數**

* **I-Isolation (隔離性)**
* 大家同時操作也不會互相打架
* A -> B 後再 B -> C 時，兩筆交易會排隊，互不干擾

* **D-Durability (持久性)**
* 一旦交易成功，資料就永遠不會消失
* 交易成功後，不管發生什麼，資料就是要在

### 資料庫的 Index
用於加速 `SELECT` 的查詢速度
* 沒有 Index 的時候，需要將資料庫翻一遍來尋找
* 有 Index 加上資料結構 (如 B-Tree)，則可在 O(logN) 的時間快速定位資料的位置

天下沒有白吃的午餐，使用 Index 的代價是：
* **拖慢寫入的速度**：修改內容時，資料庫也要同步修改 Index
* **占用儲存空間**：Index 本身也是資料，需要額外的硬碟空間

## 資料庫正規化

### 1NF
* 一個欄位只有單一值
* 去除意義上重複的欄位
* 決定主鍵

### 2NF
* 消除部分相依

> 新增新的 table 保存一直出現的欄位
> 使用 foreign key 關聯這些 table

### 3NF
* 移除遞移相依

### BCNF
經過 3NF 後，如果主鍵是由多個欄位組成，需進行 BCNF

## 程式語言

### Macro v.s. Function
| 特性 | Macro (巨集) | Function (函數) |
| :--- | :--- | :--- |
| **處理者** | 前處理器 (Preprocessor) | 編譯器 (Compiler) |
| **原理** | 文字複製貼上 | 程式碼跳轉 (Call Stack) |
| **型別檢查** | **無** | **有** |
| **執行速度** | **快** (無 overhead) | **慢** (有 overhead) |
| **編譯速度** | **慢** (程式碼膨脹) | **快** (程式碼僅一份) |
| **除錯** | 困難（惱） | 簡單（喜） |
| **陷阱** | 運算子優先序（悲） | 基本沒有 |

### 記憶體區段
#### Text Segment
* 又稱為 **Code Segment**
* 用來放置執行中的機器程式碼
* 該區段是唯讀的，你敢在執行時去修改它，OS 就會直接把你撅了 (確信)

#### Initalized Data Segment
* 又稱為 **Data Segment**
* 包含已經定義且有初始值的 **全域** 與 **靜態變數**
* 分為 **唯讀區域** 與 **可讀寫區域**
* **唯讀區域**：用來放常數，例如：`const int i = 1; char *str = "1919"`
* **可讀寫區域**：存放隨執行而改變的變數，例如全域變數、靜態變數等

#### Uninitalized Data Segment
* 又稱為 **BBS Segment**，BBS => Block started By Symbol
* 儲存未給定初始值的全域變數，如：`int a`
* 為了節省執行檔的空間，這些變數不會真的存一個「未定義」的值在檔案裡。程式載入時，OS 會幫你把這整塊記憶體都初始化為 `0` (homo 特有的溫柔)

#### Stack
* 負責處理 **函數呼叫** 的事宜：
* 區域變數
* 函數參數
* 回傳地址
* 呼叫一個函數，就疊上一個新的區塊；函數結束時，將區塊卸載
* Stack 是向下生長的

#### Heap
* 用來配置動態記憶體的區段
* `malloc` 來的空間，但要記得 `free`，不然會造成 **Memory leak**
> 釋放了有獎勵，沒釋放有懲罰
> 獎勵與懲罰並不一樣，不是會員制餐廳的心得 (悲)
* 由 BSS 上面開始向上增長

### 記憶體錯誤
#### Segmentation Fault
這不是你的程式自己崩潰，而是作業系統看你亂搞，**決定親手把你撅了** (悲)，以保護其他程式
* 當程式想要讀取 **不屬於自己** 或 **禁止存取** 的區段時發生
* 發生方法可以分成幾種：
* 對 `NULL` 指標進行參考

        int* ptr = 0;
        *ptr = 1919810

* 陣列越界

        int arr[100] = {};
        arr[1000] = 114514;

* 寫入唯讀記憶體

        char* str = "hello";
        str[0] = 'H';

* 使用已經 `free` 的指標

### 物件導向原則

#### SOLID 五大原則
* S-Single Responsibility Principle
* 單一職責原則
* 一個 class 應該專注做好一件事情

* O-Open/Closed Principle
* 開放封閉性原則
* 要增加新功能時，我們應該去 **增加** 程式碼，而不是 **修改** 程式碼
* 多用抽象與多形
* L-Liskov Subsitution Principle
* 里氏替換原則
* **子類別** 必須能夠做到 **父類別** 能做到的所有事情
* `正方形` 不應該繼承 `矩形`

* I-Interface Segregation Principle
* 介面隔離原則
* 使用者不該被迫使用 **對他們而言** 無用的功能
* 例如我們設計了萬用的影印機介面，內容包含 `影印` `掃描` `傳真`
* 看起來我們設計了一個萬能介面，很棒吧
* 但實際使用上，當我們接入一個便宜印表機，而這台印表機只會進行 `列印`
* 這個情況下假如有人用你的介面啟動 `掃描` 或 `傳真`，程式就掛了，因為你的便宜影印機根本不會

* D-Dependency Inversion Principle
* 依賴反轉原則
* 高層模組不應該依賴低層模組，應該依賴於 **介面**

## 綜合知識
### HTTP
#### CRUD Methods
* `GET`：從伺服器取得資料
* `POST`：往伺服器發送資料，創建資源
* `PUT`：更新並取代資源
* `PATCH`：更新部分資源，通常不會取代
* `DELETE`：刪除資源

#### HTTP Status code
* `100-199` 資訊回應
* `200-299` 成功回應
* `200 ok`：請求成功
* `201 Created`：請求成功並建立新資源
* `300-399` 重新導向訊息
* `301 Move Permanenty`：資源被移動到新位置
* `302 Found`：需臨時重新導向，之後可以繼續用同樣的 URI
* `400-499` 用戶端錯誤訊息
* `400 Bad Request`：用戶使用錯誤的請求方式，伺服器無法或不處理該請求
* `401 Unauthorized`：用戶身分未驗證
* `403 Forbidden`：用戶端沒有訪問該資源的權限
* `404 Not Found`：伺服器找不到請求的資源
* `405 Method Not Allowed`：使用不對的 Method 操作該資源
* `409 Conflict`：請求存在衝突
* `500-599` 伺服器錯誤訊息
* `500 Internal Server Error`：伺服器遇到不知如何處理的狀況

### RESTful API (REpresentational State Transfer)
REST 並非協定，而是一種「風格」。符合 REST 風格的 Web API 則稱為 RESTful API。

#### 用途
使用傳統方法的 Web API 時，假如我要對資源進行各種操作：
* `/getresource`
* `/updateresource`
* `/deleteresource`

API 的請求會長這樣，而採用 RESTful API 則可以改成：
* `GET /resource`
* `POST /resource`
* `DELETE /reource`

由於 RESTful API 通常由以下方法進行定義：
* 動詞：HTTP 的操作 (GET、POST、DELETE...)
* 名詞：請求的路徑

透過這個可以讓 API 使用者不須特別了解命名規則，也省得後端設計需要命名一堆網址

### API v.s. SDK
* **API: Application Programming Interface**：應用程式介面
* 用以定義多個軟體之間可以進行的互動
* 提供 **抽象化** 的方法，使開發人員無需知道內部的運作邏輯，也能順利使用其提供的功能
* **SDK: Software Development Kit**：軟體開發工具套件
* 輔助開發某項軟體的相關工具
* 公司想開發某個軟體，但不想要從頭開始研發，則可以尋找現有的 SDK，節省人力及成本

### Hashing, Encoding, Encryption
* **Hashing 雜湊**：將資料 (明文) 轉為便於搜尋的資料結構
* **不是加密**
* 雜湊無法反推
* 明文有所改變，雜湊就會有所改變 => 雜湊是 **獨一無二** 的

* **Encoding 編碼**：將資訊由原本的形式轉為電腦數字形式的過程
* 為了 **相容性** 而存在
* 例：文字檔 => `utf-8`
* 在只能傳輸文字檔的情況下 (email)，可將執行檔、圖片 **encode** 成 `base64` 即可使用文字傳輸，傳輸完畢後 **decode** 即可得到原檔案

* **Encryption 加密**：將資料變成授權方才能理解的格式
* 有去有回
* **明文** 利用 **金鑰** 加密得到 **密文**
* **密文** 需要 **金鑰** 才得以解開