111 年 國立臺灣大學生物機電系碩士班丙組《計算機概論（A）》

核心觀念

本題考查邏輯閘的布林函數表示，以及德摩根定理。閘輸出端的小圓圈代表反相：上方閘與最末閘是 NAND 閘，下方閘是 AND 閘。

德摩根定理為：

解題方法

先依訊號流向，分別寫出上方閘、下方閘的輸出，再代入最末閘。

上方 NAND 閘的輸入為 $A$ 與 $\overline{B}$，故其輸出為：

下方 AND 閘的輸入為 $\overline{C}$ 與 $D$，故其輸出為：

最末 NAND 閘將 $X$ 與 $Y$ 作為輸入，因此：

核心觀念

文法由非終結符、終結符及產生式構成。非終結符可依產生式繼續展開；終結符是推導完成後留下的符號。句子的推導結果，也可用解析樹呈現：根節點是開始符號，每個內部節點依照一條產生式展開，葉節點由左至右讀出的字串就是句子。

解題方法

(a) 由產生式左側可辨認非終結符；右側出現的符號中，凡不屬於非終結符者都是終結符。題目明確將 $ 寫在產生式中，因此它也是本題文法的終結符。

• 非終結符：$\{S,A,B\}$
• 終結符：{x, y, z, $}

(b) 依照開始符號 $S$ 推導。目標字串在 $ 前是 xyzzz。先由 S → AB$，再讓 $A$ 產生開頭的 $x$，接著 $A\to B$；前一個 $B$ 產生 yzz，後一個 $B$ 產生 z：

核心觀念

RSA 先選兩個質數 $p,q$，計算模數 $n=pq$ 與歐拉函數 $\varphi(n)=(p-1)(q-1)$。加密指數 $e$ 必須滿足 $\gcd(e,\varphi(n))=1$；解密指數 $d$ 則是 $e$ 在模 $\varphi(n)$ 下的乘法反元素，也就是

因此，$ed$ 除以 $\varphi(n)$ 的餘數必須為 $1$。

解題方法

題目給定 $p=11$、$q=7$，先計算：

接著選一個與 $60$ 互質的 $e$。取 $e=7$，因為 $\gcd(7,60)=1$，符合加密指數條件。

核心觀念

本題考查開放定址法中的線性探測。雜湊表長度為 $10$，索引範圍是 $0$ 到 $9$。每個鍵先依雜湊函數計算起始位置：

若起始位置已被占用，就依序檢查下一格，直到找到空格為止。探測位置會在表尾循環回表頭，但本題不需要循環。

解題方法

依題目給定的鍵值順序逐一插入；每次遇到碰撞，就往下一個索引探測。

核心觀念

這題考三種速率／延遲的區別：

• 傳輸延遲：把整個封包的位元送上傳輸媒介所需的時間，公式為「封包位元數 ÷ 傳輸速率」。
• 傳播延遲：訊號沿媒介從一端傳到另一端所需的時間，公式為「媒介長度 ÷ 訊號傳播速度」。
• 有效傳輸率：名目傳輸率經效率折減後，再按封包中真正承載資料的比例計算。

以下將題目的 $59\%$ 視為媒介傳送效率，並將 30 bytes overhead 視為不承載有效資料的封包負擔。

解題方法

a) 傳輸延遲

封包大小為 128 bytes，換算成位元：

乙太網路傳輸速率為 $10\ \text{Mbps}=10^7\ \text{bits/sec}$，因此：

b) 傳播延遲

同軸電纜長度為 $2.5\ \text{km}=2500\ \text{m}$，訊號傳播速度為 $2.3\times 10^8\ \text{m/sec}$：

核心觀念

12 位元 Hamming code 的檢查位元放在由右至左編號的第 $1、2、4、8$ 位，分別是 $c_1、c_2、c_4、c_8$。採用偶同位時，每個檢查位元所涵蓋的位置，其位元總和必須為偶數；等價地說，這些位元的 XOR 結果為 $0$。

依 12 位元標準位置排列，題幹字串中重複的 $d_4$ 視為排版誤植，位置如下：

解題方法

先利用 $c_1$ 的檢查範圍求 $A$。$c_1$ 檢查位置 $1、3、5、7、9、11$，也就是：

核心觀念

二元搜尋樹（BST）中，每個節點都滿足：左子樹的鍵值小於該節點，右子樹的鍵值大於該節點。

前序走訪順序為「根 → 左子樹 → 右子樹」，所以序列的第一個值是根。重建時，依 BST 的大小規則將後續節點分到左右子樹；後序走訪則是「左子樹 → 右子樹 → 根」。

解題方法

前序序列為：

第一個值 $30$ 是根。接著依大小關係建立左右子樹：

• 小於 $30$ 的節點屬於左子樹：$20, 10, 15, 25, 23$。
• 大於 $30$ 的節點屬於右子樹：$39, 35, 42$。
• 左子樹以 $20$ 為根。$10$ 小於 $20$，位於左側；$25$ 大於 $20$，位於右側。$15$ 小於 $20$、但大於 $10$，因此是 $10$ 的右子節點；$23$ 小於 $25$，因此是 $25$ 的左子節點。
• 右子樹以 $39$ 為根。$35$ 小於 $39$，位於左側；$42$ 大於 $39$，位於右側。

a) 二元搜尋樹

核心觀念

本題考查 8086 組合語言的資料寬度、算術指令，以及 DIV 的隱含被除數與商、餘數位置。

DIV BL 的除數是 8 位元暫存器 BL。執行 8 位元除法時，處理器以 AX 為被除數，將商存入 AL、餘數存入 AH。

解題方法

依序追蹤指令執行後的暫存器值：

1. MOV AX, A：令 AX = A。
2. MOV BL, B：令 BL = B。
3. ADD AX, 2：令 AX = A + 2。
4. MOV CL, 3、SUB BL, CL：令 BL = B - 3。
5. DIV BL：以 AX 除以 BL，商存入 AL。
6. MOV SUM, AL：將商存入 SUM。

核心觀念

選擇排序（selection sort）每一回合都在尚未排序的區間中找出最小值，並將它與區間最左側的元素交換。完成一回合後，最左側的位置便確定為目前區間的最小值；接著縮小未排序區間，直到全部排好。

解題方法

原始資料為 $[20,12,10,15,2]$。依序找出每一輪未排序區間的最小值：

以 Python 實作如下：

核心觀念

孿生質數是兩個質數，且相差 $2$。因此只要由小到大檢查每個整數 $p$，判斷 $p$ 與 $p+2$ 是否皆為質數，就能找出所有孿生質數對。

本題適合使用埃拉托斯特尼篩法。質數 $n$ 的合數倍數可由其質因數標記；篩到 $\sqrt{n}$ 即可，因為若 $n$ 是合數，至少有一個因數不大於 $\sqrt{n}$。

解題方法

題目要求兩個數都小於 $10000$，所以令上限為 $10000$，建立索引為 $0$ 到 $9999$ 的布林陣列 is_prime。初始時假設每個數都是質數，再依序將合數標記為 False。

對每個未被標記的質數 $p$，從 $p^2$ 開始標記其倍數。小於 $p^2$ 的倍數已會由更小的質因數標記，因此可從 $p^2$ 起算。完成篩選後，逐一檢查 $p$ 和 $p+2$；兩者皆為質數時輸出該數對。