114 高普考高考三級 電信工程 計算機概論 考古題詳解

核心觀念

本題考查基本邏輯閘的真值表，以及如何以 AND、OR、NOT 組合出 $2$ 對 $1$ 多工器（Multiplexer，MUX）。

多工器依選擇線 $S$ 的值，將兩個資料輸入端之一送至輸出端。其布林函數為

其中 $\overline{S}$ 表示 $S$ 的反相。

AND、OR 與 NOT 真值表

AND 閘只有在所有輸入皆為 $1$ 時，輸出才為 $1$；OR 閘只要有任一輸入為 $1$，輸出便為 $1$；NOT 閘則將輸入反相。

解題方法

分別處理兩種選擇狀態：

• 當 $S=0$，$\overline{S}=1$，所以 $\overline{S}\land I_0=I_0$；同時 $S\land I_1=0$。因此 $Y=I_0$。
• 當 $S=1$，$\overline{S}=0$，所以 $\overline{S}\land I_0=0$；同時 $S\land I_1=I_1$。因此 $Y=I_1$。

將這兩個受選擇線控制的 AND 輸出，接到同一個 OR 閘，即可得到多工器的輸出。

電路圖

核心觀念

本題考查 NAND Flash 的每個儲存單元（cell）可記錄的位元數。單元可分辨的電荷狀態越多，就能在同一顆晶片中儲存越多資料；但狀態間的判讀界線也越密，控制與讀取較複雜，寫入速度、耐用度通常較低。

每個儲存單元可表示的狀態數為 $2^b$，其中 $b$ 是每單元儲存的位元數：

此處的「層」是每個記憶單元記錄的位元數，不是 NAND 晶片堆疊的實體層數。

解題方法

依序比較每單元的位元數，再由狀態數推論使用者關心的特性：單元記錄的狀態越多，單位容量的製造成本通常越低；但電荷狀態較難精確寫入及辨識，通常會使原生寫入速度降低、可承受的寫入／抹除次數減少。

因此整體趨勢為：每單元位元數增加時，容量密度提高、每 GB 成本下降，但原生寫入速度與耐用度通常下降。

四種 NAND Flash 比較

核心觀念

本題考查兩種密碼學的金鑰使用方式，以及公鑰、私鑰與非對稱式密碼學的關係。

• 對稱式密碼學：加密與解密使用同一把金鑰，或使用可由彼此直接推導的金鑰。通訊雙方須事先安全地共享金鑰。
• 非對稱式密碼學：使用一組數學上相關、但不能由公開的一把有效推導另一把的金鑰，分別稱為公鑰與私鑰。公鑰可公開，私鑰須由持有人妥善保管。

解題方法

作答時先比較兩類密碼學的金鑰數量與管理方式，再說明公鑰和私鑰如何分別支援機密性與身分驗證。

一、對稱式密碼學

傳送者與接收者共同持有秘密金鑰 $K$。傳送者以 $K$ 將明文 $M$ 加密，接收者再以同一把金鑰解密：

其中 $C$ 為密文，$E$ 為加密函數，$D$ 為解密函數。常見演算法包括 AES。

此類演算法運算效率高，適合大量資料加密；主要挑戰是雙方如何安全地建立及交換共享金鑰。若每一對通訊者都要各自持有秘密金鑰，使用者數量增加時，金鑰管理也會變得複雜。

二、非對稱式密碼學

每位使用者持有一組金鑰：可公開給他人的公鑰 $K_{\text{pub}}$，以及由本人保管的私鑰 $K_{\text{priv}}$。這兩把金鑰在數學上彼此相關，具有特定的加解密或簽章驗證關係。

核心觀念

本題考查主機連上網際網路時，TCP/IP 網路設定中四項資訊各自負責的工作：識別主機、判斷目的地是否在本地網路、將封包送往其他網路，以及把網域名稱轉換成 IP 位址。這四項設定彼此配合，使電腦能找到目的地並與之通訊。

解題方法

依封包傳送的順序理解各項功能：

1. 主機以 IP 位址作為網路上的位址。
2. 子網路遮罩協助判斷目的 IP 是否與本機位於同一個子網路。
3. 目的地在其他網路時，將封包交給預設閘道轉送。
4. 使用者輸入網域名稱時，透過 DNS 查詢其對應的 IP 位址。

四項設定的功能

1. IP 位址

IP 位址是網路介面在 IP 網路中的邏輯位址，用來識別主機或網路介面，並作為封包傳送的來源位址或目的位址。

例如，電腦要與另一台主機通訊，封包必須帶有適當的來源 IP 與目的 IP，網路設備才能依目的位址轉送。

2. 子網路遮罩

子網路遮罩用來區分 IP 位址中的網路部分與主機部分，協助電腦判斷某個目的 IP 是否位於本機子網路。

電腦會依 IP 位址與子網路遮罩判斷目的主機是否在同一個子網路：

• 若在同一子網路，電腦可直接在本地網路尋找目的主機。
• 若不在同一子網路，電腦便將封包送往預設閘道。

以常見的 IPv4 設定為例，遮罩 255.255.255.0 對應前 24 位元的網路部分；主機端會依此判斷目的位址是否屬於同一個網路。

3. 預設閘道 IP 位址

核心觀念

演算法是為了解決特定問題而設計的一組明確、有限且可執行的步驟。從計算機科學的觀點，演算法通常須具備：

• 輸入：可有零個或多個輸入資料。
• 輸出：至少產生一個結果。
• 明確性：每一步驟的內容與執行方式都清楚無歧義。
• 有限性：經有限步驟後必須停止。
• 有效性：每一步都能由計算機實際執行，並在有限時間內完成。

本題比較循序搜尋與二元搜尋的時間效率。以「鍵值比較一次」作為一個運算單位；假設搜尋目標存在於陣列中，且在 $N$ 個位置上等可能出現。循序搜尋未命中時需檢查全部 $N$ 個元素；若需一併分析未命中情況，其比較次數也是 $N$。

解題方法

循序搜尋（Sequential Search）

循序搜尋由陣列開頭逐一比較，直到找到目標或檢查完全部元素。

• 適用時機：資料未排序、資料量小，或只搜尋少數次。陣列不必事先整理。
• 最小搜尋時間：目標在第一個位置，需 $1$ 次比較。
• 平均搜尋時間：目標在 $N$ 個位置上等可能出現，平均比較次數為

• 最大搜尋時間：目標在最後一個位置，或目標不在陣列中，需 $N$ 次比較。

因此循序搜尋的平均與最壞時間複雜度皆為 $O(N)$。

二元搜尋（Binary Search）

二元搜尋每次檢查目前搜尋範圍的中間元素，再依大小關係保留左半或右半範圍，直到找到目標或搜尋範圍為空。

• 適用時機：陣列必須依搜尋鍵值排序，且能有效取得中間位置；適合資料量較大或需要重複搜尋的情況。若資料尚未排序，需先排序，排序成本也應納入整體考量。
• 最小搜尋時間：第一次比較中間元素即找到目標，需 $1$ 次比較。
• 最大搜尋時間：每次比較將搜尋範圍約減半。最壞比較次數為