民國115年 高考三級 電力工程 計算機概論考古題
民國115年 高考三級 電力工程 計算機概論收錄考選部官方試題，共 5 題可線上瀏覽，考選部未公告本科目答案。
題目與答案
使用筆電透過家裡或hot spot 的WiFi 上網，如果碰到卡卡的不太順的
時候，檢查相關的軟硬體或設定均沒問題，那可能會有其他什麼原
因？請列舉兩個常見的可能原因，說明為何會造成網路卡卡的，那又
分別該如何解決這些因素。（10 分）
IEEE 802.11 的標準，RTS/CTS 主要解決了什麼問題？為什麼它可以
解決這個問題？請說明之。（10 分）
參考解答（AI 生成，非官方）
- 一、無線電干擾與通道壅塞：2.4 GHz 僅少數非重疊通道，鄰近 AP、藍牙、微波爐同時競爭，CSMA/CA 的退避與重傳增加，造成延遲、抖動。解決方式是改用 5 GHz/6 GHz、選擇 1、6、11 較空通道、調整通道寬度與 AP 位置，並以頻譜工具找出干擾源。
- 二、上游頻寬不足或訊號品質不佳：ISP 尖峰壅塞、AP 上行頻寬不足、距離遠或隔間衰減，會使 SNR 下降、速率退化並重傳；多人串流、雲端備份亦可能佔滿頻寬。解決方式是採用有線回傳、升級頻寬、設定 QoS 限流，並靠近 AP 或以 Mesh、有線延伸改善涵蓋。
- 三、診斷時可先分段測試：ping 預設閘道確認無線區、ping 外部 IP 確認上游、查 DNS 解析確認名稱服務，並觀察不同時段與裝置是否同樣卡頓。如此可區分無線干擾、ISP 壅塞或終端設定問題，避免只重開機而無法對症下藥。
- 四、RTS/CTS 主要解決隱藏節點（hidden node）問題：無線站台靠載波感測判斷媒介是否空閒，但兩個站台彼此聽不到、卻都聽得到 AP 時，可能同時傳送而在 AP 端碰撞。RTS/CTS 由傳送端先送 RTS，AP 回覆 CTS，讓通道先被預約。
- 五、其原理是 CTS 會被 AP 涵蓋範圍內的其他站台收到，這些站台依 CTS 的 duration 更新 NAV，在預約期間延後傳送，形成虛擬載波感測；即使彼此隱藏，也會因 CTS 而避開。限制是控制訊框仍有碰撞與額外負擔，故常以 RTS threshold 調整，小訊框通常關閉。
請問下列的C 語言函式xxxSort()是在執行那種排序演算法？請說明
理由。（10 分）
void xxxSort(int arr[], int n)
{
int i, j, key;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
費氏數列的定義為：
F(0)=0, F(1)=1
F(n)=F(n−1)+F(n−2), n≥2
假設我們要寫一個程序來算出F(n)，可以用遞迴（recursive）方式，也
可用迭代（iterative）方式來寫程式。請問這兩種方式的優缺點為何？
（10 分）
參考解答（AI 生成，非官方）
- 一、這是插入排序（Insertion Sort）。外層 i 從 1 到 n-1，將 arr[i] 存為 key；內層 j 由 i-1 往前，將大於 key 的元素右移，最後把 key 放入 arr[j+1]，使前 i+1 個元素保持排序。
- 二、理由是其迴圈不變式為「arr[0..i-1] 已排序」，每回合把未排序區的第一個元素插入已排序區的正確位置，作法如同整理撲克牌。最壞與平均時間 O(n^2)、最佳 O(n)、額外空間 O(1)，且為穩定排序；適合小資料或近乎排序，資料量大時搬移成本高。
- 三、遞迴版費氏數列直接依 F(n)=F(n-1)+F(n-2) 計算，終止條件為 F(0)=0、F(1)=1。優點是程式簡潔、與數學定義一致、容易驗證；缺點是未記憶化時會重複計算相同子問題，時間複雜度達 O(2^n)，且遞迴深度 O(n)，n 大時可能堆疊溢位。
- 四、迭代版以 a=0、b=1，迴圈執行 n 次更新 a、b，時間 O(n)、空間 O(1)，沒有函式呼叫與堆疊負擔，可穩定計算較大的 n；缺點是程式較不直觀，需正確處理 n=0、n=1 的邊界，數值過大時仍有整數溢位問題。若採備忘錄或動態規劃，遞迴可降為 O(n)。
- 五、取捨上，教學或驗證定義可用遞迴；實務重視效率與大 n 時宜用迭代，或使用遞迴加記憶化。若 n 超過資料型別範圍，還需改用大數運算，不能只依賴固定位元整數。
A 與B 均為1-bit 的輸入端，設計一個1-bit 的互斥或（XOR）線路，
判斷A 是否與B 一樣，若一樣則輸出0，否則輸出1。而且只能使用
AND、OR、NOT 邏輯閘（Gate）。（10 分）
A 與B 均為1-bit 的輸入端，設計一個1-bit 相等（EQUAL）的線路，
判斷A=B，若true 則輸出1，否則輸出0。而且只能使用AND、OR、
NOT 邏輯閘（Gate）。（10 分）
參考解答（AI 生成，非官方）
- 一、XOR 的定義是 A 與 B 不同時輸出 1，相同時輸出 0；真值表為 00→0、01→1、10→1、11→0。其布林式可寫成 F=A'B+AB'，也可寫成 F=(A+B)(AB)'，兩者都只使用 AND、OR、NOT 即可實現。
- 二、第一種接法：A、B 各經 NOT 得 A'、B'；A' 與 B 接 AND 得 A'B，A 與 B' 接 AND 得 AB'；兩個 AND 輸出再接 OR，即得 XOR。此為標準積之和（SOP）電路，訊號由左向右、輸入在上、輸出在下繪製。
- 三、第二種等價接法：A、B 先接 OR 得 A+B；A、B 再接 AND 後經 NOT 得 (AB)'；最後將兩者接 AND，輸出 F=(A+B)(AB)'。此接法使用一個 OR、兩個 AND、一個 NOT，考生繪圖時應標明各節點名稱與真值。
- 四、EQUAL 的定義是 A=B 時輸出 1，否則輸出 0，即 XNOR；真值表為 00→1、01→0、10→0、11→1。布林式為 F=AB+A'B'，也可表示為 F=(A XOR B)'，電路只需在 XOR 輸出後接 NOT。
- 五、以 AND-OR 實作時，A、B 接 AND 得 AB；A、B 各經 NOT 後接 AND 得 A'B'；兩者再接 OR 即為 EQUAL。繪圖時左側畫 A、B 輸入與 NOT 分支，中間畫兩個 AND，右側畫 OR 與輸出 F，並標示 A'、B'、AB、A'B' 等接線。
在多執行緒（multithread）的作業系統，可能會有飢餓（starvation）或死
結（deadlock）的問題，請問它們各自是怎樣的情況會造成這樣的問題。
請各提出一個解決的方法，並說明為何可以解決問題。（20 分）
參考解答（AI 生成，非官方）
- 一、飢餓（starvation）是指某執行緒長期得不到所需資源或 CPU，雖然系統仍有其他執行緒在進展，但該執行緒的等待時間沒有上限。常見於固定優先權排程，低優先權執行緒不斷被高優先權執行緒插隊，或資源分配政策偏向特定對象。
- 二、解決飢餓可用老化（aging）：隨等待時間增加逐步提高該執行緒的優先權，使其最終能取得資源；也可採公平排程、FIFO 或保證最小服務配額。為何有效？因為把等待時間納入排程決策，可消除「永遠有更高優先權者」的無界延遲，提供有界等待。
- 三、死結（deadlock）是指兩個以上執行緒互相持有對方所需的資源，並永久等待對方釋放，導致全部無法前進。形成死結通常需同時滿足四條件：互斥、持有並等待、不可剝奪、循環等待；例如 T1 持有 R1 等 R2，T2 持有 R2 等 R1。
- 四、解決死結可採預防：將資源編號，規定只能依遞增順序申請，破壞循環等待；或一次申請全部資源，破壞持有並等待；亦可允許資源剝奪。避免法如 Banker's algorithm 在分配前檢查是否仍處安全狀態；偵測法則建立 wait-for graph，找出循環後終止、回滾或搶占。
- 五、兩者不同：老化只處理排程不公平造成的延遲，不能打破循環等待；死結預防可能降低資源利用率，避免法需事先知道最大需求，偵測法有額外負擔。實務上常以資源排序、逾時機制與偵測回收搭配使用，並以公平排程降低飢餓風險。
請將下列中序式（infix）的表示式，轉成前序式（prefix）。（10 分）
5 + 8 * (7 – 3) + 6
下列兩個IP，根據它的遮罩，請判定是否屬於同一個子網路（subnet）？
（10 分）
200.188.170.82/27 與200.188.170.114/27
參考解答（AI 生成，非官方）
- 一、中序轉前序須先依優先權與括號建立運算式樹，乘除優先於加減，括號最優先。原式可改寫為 ((5+(8*(7-3)))+6)；前序遍歷的順序是「運算子、左子樹、右子樹」，因此又稱波蘭前置表示法。
- 二、逐步轉換：先處理 7-3 得「- 7 3」；8 乘該結果得「* 8 - 7 3」；5 加該結果得「+ 5 * 8 - 7 3」；最後加 6 得「+ + 5 * 8 - 7 3 6」。驗算：7-3=4，8*4=32，5+32=37，37+6=43，與原式相符。
- 三、子網路判定先求遮罩：/27 表示前 27 位為網路位，遮罩為 255.255.255.224，主機位 5 位，區塊大小為 2^5=32。網路位址=IP AND 遮罩，可用主機範圍為網路位址加 1 至加 30，廣播位址為加 31。
- 四、計算 200.188.170.82/27：82 AND 224 = 64，故網路位址為 200.188.170.64，範圍 64 至 95；200.188.170.114/27：114 AND 224 = 96，網路位址為 200.188.170.96，範圍 96 至 127。
- 五、結論：兩者分別位於 200.188.170.64/27 與 200.188.170.96/27，不在同一個子網路；若要互相通訊，須經路由器轉送或調整遮罩。判斷時不可只看 IP 前幾碼，必須以遮罩計算網路位址。