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

核心觀念

本題考查編譯器將高階語言轉換成機器語言的工作流程。編譯器不是單純逐字替換指令，而是先分析程式的語法與語意，再產生適合目標處理器執行的機器碼。典型編譯流程可分為前端分析、中介表示與最佳化、後端程式碼產生，以及組譯與連結等步驟。

解題方法

作答時依照程式由原始碼到可執行程式的處理順序說明各階段，並交代每階段的輸入、工作與輸出：

1. 詞彙分析（lexical analysis） 詞彙分析器讀取原始程式字元，依照語言規則辨認關鍵字、識別字、常數、運算子及分隔符號等詞彙單位（token），並移除註解與不具語意的空白。識別字及其相關資訊可記錄在符號表中。若有無法辨認的字元或詞彙，會回報詞彙錯誤。

2. 語法分析（syntax analysis） 語法分析器依文法規則檢查 token 的排列是否合法，並建立語法樹或抽象語法樹。例如，判斷運算式中的括號、運算子及運算元是否符合文法。若結構不符合文法，會回報語法錯誤。

3. 語意分析（semantic analysis） 語意分析器檢查程式是否符合語言的語意規則，包括識別字是否已宣告、變數型別是否相容、函式呼叫的參數是否正確，以及作用範圍是否適當等。此階段會使用或更新符號表，並可進行型別檢查與必要的型別轉換。

4. 中介碼產生（intermediate code generation） 編譯器將語法樹轉換為與特定處理器無關或依賴程度較低的中介表示，例如三位址碼。以 x = a + b * c 為例，中介碼可寫成：

這種表示保留運算順序，也便於後續最佳化與移植到不同目標平台。

核心觀念

二分搜尋法（binary search）利用「資料已依序排列」這項前提，每次檢查搜尋範圍中間的元素，再排除不可能含有目標值的一半範圍。它考查的是有序資料的搜尋策略，以及每次將候選範圍縮小一半所帶來的時間複雜度。

若陣列索引範圍為 $low$ 至 $high$，中間位置可取：

若目標值 $x=A[mid]$，搜尋成功；若 $x<A[mid]$，則只需搜尋左半部；若 $x>A[mid]$，則只需搜尋右半部。當 $low>high$ 時，代表搜尋範圍已空，目標值不存在。

解題方法與範例

以遞增陣列 $A=[3,7,11,18,23,29,34,41]$ 搜尋 $x=29$ 為例，索引由 $0$ 開始：

每次比較都能依排序關係排除一半候選元素，因此不必逐一檢查整個陣列。

效能分析

核心觀念

本題考「卡諾圖化簡」與「最簡積項之和」（最簡 SOP）。將 minterm 編號轉成 $WXYZ$ 的二進位值，在卡諾圖中把相鄰的 $1$ 合併成大小為 $1、2、4、8$ 等 $2$ 的冪次方的矩形。每組中的變數若有變化就消去，固定為 $1$ 的變數保留原變數，固定為 $0$ 的變數保留反變數。

卡諾圖的相鄰關係包含邊界環接；每個最小項都必須至少被一組涵蓋。

解題方法

以 $WX$ 為列、$YZ$ 為欄，兩方向皆依 Gray code 排列 $00、01、11、10$。依題目填入各最小項：

接著找出最大的相鄰群組：

1. $m_0,m_2,m_8,m_{10}$ 可組成四格。這組跨越卡諾圖左右邊界，固定 $X=0、Z=0$，故化為 $\overline{X}\,\overline{Z}$。

核心觀念

程序間通訊（Interprocess Communication, IPC）是作業系統提供的機制，讓不同程序能交換資料並協調執行。IPC 的兩種基本模式是：

1. 共享記憶體（shared memory）：程序共同存取一塊記憶體區域。
2. 訊息傳遞（message passing）：程序透過作業系統提供的傳送與接收操作交換訊息。

解題方法

依資料如何在程序間流動，分別說明其工作原理，以及作業系統在其中扮演的角色。

一、共享記憶體

作業系統先建立一塊可供多個程序存取的共享記憶體區域，並將該區域映射至各程序的位址空間。程序之後可直接讀取或寫入這塊記憶體，藉此交換資料。

由於多個程序可能同時存取共享資料，必須搭配同步機制，例如鎖、信號量或監視器，避免競爭條件與資料不一致。此模式的資料傳輸效率高；但共享區域建立後，程序間的讀寫協調主要由程序自行負責。

二、訊息傳遞

核心觀念

快速排序法（Quick Sort）是採用「分治法」（divide and conquer）的排序演算法。它選取一個樞紐值（pivot），將資料分割成兩部分：一部分的鍵值不大於樞紐值，另一部分的鍵值不小於樞紐值。接著對兩部分分別遞迴排序，直到子序列長度為 0 或 1。

分割完成時，樞紐值已位於最終排序位置；但左右兩部分在排序完成前不一定有序。快速排序通常在原陣列中交換元素完成分割，平均額外空間用於遞迴呼叫的堆疊。

解題方法與操作範例

以序列 $[6, 3, 8, 5, 2, 7, 4]$ 為例，選最後一個元素 $4$ 為 pivot。分割時，將小於或等於 $4$ 的元素移至左側：

此時 $4$ 已在其最終位置，左側為 $[3,2]$，右側為 $[5,6,7,8]$。分別遞迴排序：

• 左側 $[3,2]$ 排成 $[2,3]$。
• 右側 $[5,6,7,8]$ 已有序，遞迴處理後維持不變。

最後得到：

分割的具體交換順序會因 pivot 選擇及分割程序不同而異；重點是每次分割後，pivot 左右兩側分別符合相對大小關係，再對兩側遞迴處理。

效能分析

設資料筆數為 $n$，每次分割需掃描目前子序列，因此分割成本為 $\Theta(n)$。