成大 112 年資管所計算機概論參考答案

題號	考點主題	答案
1-1	0／1 Knapsack 問題的動態規劃解法與時間複雜度（Pseudo-polynomial Time）	F
1-2	K-means 與 Hierarchical Clustering：分群演算法比較與 Feature Vector 正規化	TRUE
1-3	決策樹（Decision Tree）與集成學習法（Bagging、隨機森林、Boosting）	TRUE
1-4	K-means 與 Hierarchical Clustering：分群演算法比較與 Feature Vector 正規化	TRUE
1-5	疊代式數值演算法收斂速度：以精度而非輸入規模衡量（Newton's Method 範例）	F
2-1	執行緒同步機制：鎖與 Starvation	(d)
2-2	執行緒同步機制：鎖與 Starvation	(a)
2-3	x86 呼叫慣例：函式回傳值與堆疊傳遞規則	(b)
2-4	IEEE 754 浮點數格式：位元配置與精度／範圍取捨	(c)
2-5	編譯與連結流程：從原始碼到執行檔與跨檔案重複定義錯誤	(b)

考點：IEEE 浮點數運算性質：結合律與分配律失效、單調性、型別轉換

敘述	判斷	反例
$x > 0 \Rightarrow x / 2 > 0$	False	$x = 2^{- 149}$ ， $x / 2$ 捨入為 0
$(x + y) * z = = x * z + y * z$	False	$x = 2^{100}, y = - 2^{100}, z = 2^{100}$ ：左式 0，右式 NaN
$x \geq y$ 且 $z \leq 0 \Rightarrow x * z \leq y * z$	True
$x > y \Rightarrow (d o u b l e) x > (d o u b l e) y$	True
$d > e \Rightarrow (f l o a t) d > (f l o a t) e$	False	$d = 1 + 2^{- 30}, e = 1$ ：皆捨入為 1.0
$x + 1 > x$	False	$x = 2^{24}$ ： $x + 1$ 捨回 $2^{24}$

考點：Merge Sort 與 Heap Sort 演算法邏輯

Merge Sort。前半 $[1, 3, 8, 15]$ 、後半 $[6, 10, 14, 23]$ 分別是原陣列前四個與後四個排序後的結果，為最後一次 merge 前的狀態。

考點：BFS 與 DFS：定義、範例與比較

BFS（level-order traversal），以 Queue 實作：root 先入佇列，每次取出隊首印出，再把它的子節點依序放入隊尾。

考點：記憶體定址空間計算範例

$2^{64}$ bytes

考點：Stack 與 Queue 定義與應用場景

Stack。undo 復原的永遠是最近一次動作（LIFO）：每個動作 push 進 stack，undo 時 pop 頂端動作並反向套用。

考點：十六進位與二進位轉換、無號與有號整數表示法

二進位 10100111；unsigned 167；signed $- 89$ 。

考點：初等排序：Bubble／Insertion／Selection Sort 演算法與範例

Insertion Sort 較好。近乎排序時每個元素只需少數比較即就定位，接近 $O (n)$ ；Selection Sort 每輪都要掃完剩餘元素找最小值，恆為 $O (n^{2})$ 。

考點：簡單迴圈時間複雜度分析：等差遞增 vs 等比遞增（i=i+1 vs i=i*2）

$O (n^{2})$ 。外層 i 每次加 2，約執行 $n / 2$ 次；內層執行 $n - i + 1$ 次，總和 $n + (n - 2) + (n - 4) + \dots \approx n^{2} / 4$ 。

考點：簡單迴圈時間複雜度分析：等差遞增 vs 等比遞增（i=i+1 vs i=i*2）

$O (n)$ 。第一個迴圈每次加 5，約 $n / 5$ 次；第二個迴圈每次除以 2，約 $\log n$ 次；兩迴圈依序執行， $O (n) + O (\log n) = O (n)$ 。

考點：簡單迴圈時間複雜度分析：等差遞增 vs 等比遞增（i=i+1 vs i=i*2）

$O (n)$ 。外層 i 每次乘 2，約 $\log n$ 次；內層執行 i 次，總和 $1 + 2 + 4 + \dots + \frac{n}{2} \approx n$ 。

題號	考點主題	答案
6(a)	K-means 與 Hierarchical Clustering：分群演算法比較與 Feature Vector 正規化	M. Normalization
6(b)	K-means 與 Hierarchical Clustering：分群演算法比較與 Feature Vector 正規化	O. Linkage criterion
6(c)	BFS 與 DFS：定義、範例與比較	Q. Backtracking
6(d)	Greedy Algorithm 與 Local Optima：貪婪法為何不保證全域最佳解	F. Local optima
6(e)	OOP 多型：Overloading 與 Overriding 比較，及 SOLID 五大原則	I. Specification
6(f)	Big O 化簡邏輯：只留最高階項與省略係數	H. Upper bound
6(g)	OOP 多型：Overloading 與 Overriding 比較，及 SOLID 五大原則	K. Inheritance
6(h)	遞迴與數學歸納法的關係	G. Induction
6(i)	Hash Function 與雜湊表（Hash Table）基本概念	C. Expected running time
6(j)	Merge Sort 與 Heap Sort 演算法邏輯	S. Divide and conquer

成大其他年份