108 專技高考高等考試 電子工程技師 電子計算機原理 考古題詳解

核心觀念

本題考查逐一掃描陣列以尋找最大值，以及根據迴圈次數與條件判斷次數分析時間複雜度。

演算法先將 $A[1]$ 設為目前最大值，再依序檢查 $A[2]$ 至 $A[n]$。若 $A[i]\geq\text{currentMax}$，便更新目前最大值。符號 $\geq$ 包含相等，因此遇到相同的最大值時，第 4 行也會執行。

解題方法

(一) C 或 C++ 中，賦值運算子使用 =，所以「$\leftarrow$」以 = 表示。例如：

currentMax = A[1];

(二) 依序追蹤目前最大值：

核心觀念

多項式時間是指存在固定常數 $k$，使執行時間可由 $O(n^k)$ 上界描述。依此定義，$\log_2 n$、$n$、$n\log_2 n$、$n^2$ 都屬於 polynomial-time growth；$2^n$ 與 $n!$ 則不是。

解題方法與各小題

（一）Polynomial-time growth

逐一看函數是否能以某個固定次方的 $n$ 作為上界：

• $\log_2 n$：屬於多項式時間，且成長慢於 $n$。
• $n$：屬於多項式時間。
• $n\log_2 n$：屬於多項式時間；例如對足夠大的 $n$，$\log_2 n\le n$，所以 $n\log_2 n\le n^2$。
• $n^2$：屬於多項式時間。
• $2^n$：指數成長，不屬於多項式時間。
• $n!$：階乘成長，不屬於多項式時間。

因此，屬於 polynomial-time growth 的函數是 $\log_2 n$、$n$、$n\log_2 n$、$n^2$。

（二）Merge sort

每次將資料分成兩半遞迴排序，再以線性時間合併，故遞迴式為

$T(n)=2T(n/2)+\Theta(n).$

依主定理，$T(n)=\Theta(n\log_2 n)$，對應圖中的 $n\log_2 n$。

（三）Quick sort 最糟狀況

核心觀念

本題考查作業系統中的 job 與 process、多重佇列、CPU 時間片輪替及 FIFO。依圖示，工作由 Job queue 進入處理流程；已載入記憶體且可使用 CPU 的程序排入 Ready queue；需要 I/O 的程序等待 I/O 完成，完成後回到 Ready queue。

解題方法

判讀流程圖中程序移動的原因：CPU 時間片用完，程序回到 Ready queue；程序提出 I/O 要求，就進入 I/O queue；I/O 完成後，程序再回到 Ready queue。再依作業系統的定義，說明各佇列所存放的對象及 FIFO 的服務順序。

各小題詳解

(一) 工作（job）及程序（process）的主要差別

Job 是使用者提交給電腦、等待系統處理的工作單位，通常包含程式及相關資料。Process 則是程式正在執行時的實例，具有執行狀態、程式計數器、暫存器內容及所需資源等資訊。

簡言之，job 是等待處理的工作；process 是正在執行或等待執行的程序。Job 被系統接納並載入記憶體後，會進入程序管理與排程流程。

(二)「Time slot exhausted」的意思

「Time slot exhausted」表示程序獲得的 CPU 時間片（time quantum）已用完。在分時或輪轉排程中，作業系統會暫停該程序，將它放回 Ready queue，等待下一次取得 CPU。

核心觀念

本題考查資料結構的分類、堆疊的存取順序、鏈結串列節點的欄位，以及圖形的兩種常見表示法。依題圖，Graph 為無向圖，節點為 $1,2,3,4$，邊為 $\{1,2\}$、$\{1,3\}$、$\{1,4\}$、$\{2,3\}$、$\{3,4\}$；沒有自我迴圈，也沒有連接節點 $2$ 與 $4$ 的邊。

解題方法與各小題答案

(一) Linear Data Structure 與 Non-Linear Data Structure 的差別

線性資料結構中的元素依序排列，除首尾元素外，每個元素通常各有一個前驅和一個後繼，形成單一路徑，例如 Array、Linked List、Queue、Stack。

非線性資料結構中的元素不只依單一順序排列，一個元素可以連結多個其他元素，形成階層或網狀關係，例如 Tree 和 Graph。

判斷時看元素間的組織關係：單一序列屬於線性，多分支或網狀連結屬於非線性。

(二) Static 與 Dynamic 的差別

**Static（靜態）**資料結構的容量通常在建立時就決定，執行期間不易改變；圖中例子為 Array。

**Dynamic（動態）**資料結構可依執行需求增加或移除元素，大小可變；圖中例子包括 Linked List、Queue 和 Stack。動態結構通常透過配置與釋放記憶體調整容量。

(三) 圖中何者亦稱為 LIFO？

**Stack（堆疊）**亦稱為 LIFO（Last In, First Out，後進先出）：最後放入的元素會最先取出。Queue 則是 FIFO（First In, First Out，先進先出）。

(四) LinkedList 的 data 和 link 各存什麼資訊？