首頁 / 高考三級 電信工程考古題 / 民國115年 高考三級 電信工程 計算機概論 民國115年 高考三級 電信工程 計算機概論考古題
民國115年 高考三級 電信工程 計算機概論收錄考選部官方試題，共 5 題可線上瀏覽，考選部未公告本科目答案。
題目與答案
使用筆電透過家裡或hot spot 的WiFi 上網，如果碰到卡卡的不太順的
時候，檢查相關的軟硬體或設定均沒問題，那可能會有其他什麼原
因？請列舉兩個常見的可能原因，說明為何會造成網路卡卡的，那又
分別該如何解決這些因素。（10 分）
IEEE 802.11 的標準，RTS/CTS 主要解決了什麼問題？為什麼它可以
解決這個問題？請說明之。（10 分）
參考解答（AI 生成，非官方） 一、原因之一是無線頻道壅塞與干擾。2.4 GHz 頻段只有 1、6、11 三個互不重疊的頻道，鄰居的 AP（Access Point，無線接取點）、藍牙裝置、微波爐與無線電話都會共用這段頻譜；訊框碰撞後會不斷重傳，使用者便會感到延遲升高、速率忽快忽慢。解法是用 Wi-Fi 掃描工具找出較空閒的頻道並手動固定，優先改用 5 GHz 或 6 GHz 頻段，遠離干擾源，必要時以有線回程（wired backhaul）的 Mesh 分散負載。 二、原因之二是訊號衰減與隱藏節點造成低訊噪比（SNR）。距離太遠、隔間牆與金屬遮蔽會使訊號變弱，AP 的速率調適（rate adaptation）便自動降階至較低 MCS（Modulation and Coding Scheme，調變與編碼策略），吞吐量隨之銳減；隱藏節點則讓終端在感測不到對方的情況下同時發送。解法是調整 AP 位置與天線、加裝 Mesh 節點、採用 802.11ax 與 band steering（頻段引導），並開啟 RTS/CTS。 三、IEEE 802.11 的 RTS/CTS（Request to Send / Clear to Send，請求發送／允許發送）主要解決隱藏節點問題（hidden node problem），以及無線環境難以偵測碰撞的困境。有線乙太網路可邊送邊聽，無線電收發共用天線，發送時無法偵聽，故採 CSMA/CA（Carrier Sense Multiple Access with Collision Avoidance，載波感測多重存取／碰撞避免）事先避碰；但載波感測僅涵蓋發送端鄰域，位處兩端之間卻彼此聽不到的節點仍會同時發射，而在 AP 端撞毀。 四、運作方式：發送端先送出短小的 RTS 訊框，載明此次傳輸所需時間；AP 回以 CTS，而 CTS 會被 AP 涵蓋範圍內所有節點收到。其他節點依 CTS 中的 duration（持續時間）設定網路配置向量（NAV, Network Allocation Vector），在期限內保持靜默，等於由 AP 代為宣告頻道已被預約。原本互相聽不見的隱藏節點因此被 CTS 納入同一保留區間，碰撞機率大幅降低。 五、限制與實務：RTS/CTS 會增加額外控制訊框與延遲，短訊框情況下反而降低效率，故實務多以 RTS threshold（門檻值）設定，僅在訊框超過一定長度時啟用；暴露節點（exposed node）仍可能被過度抑制。此外還須配合訊框聚合（A-MPDU）與 QoS（服務品質）機制，才能真正改善卡頓感受。
請問下列的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 起，把 arr[i] 存成 key，內層以 j=i-1 向左掃描，凡 arr[j] 大於 key 就右移一格，最後將 key 放入空出的位置。這正是把新元素插入已排序前綴的動作，維持迴圈不變式「arr[0..i-1] 已排序」，與選擇排序的元素交換、氣泡排序的相鄰交換明顯不同。 二、特性與複雜度：原地（in-place）排序，額外空間 O(1)；穩定（stable），相等元素的相對次序不變；具適應性（adaptive），資料接近排序時內層幾乎不移動，最佳情況 O(n)，最差與平均為 O(n^2)。適合小筆數或串流式、逐步到來的資料，也是許多函式庫處理小陣列時採用的混合排序（如 Timsort）之基礎。 三、遞迴（recursive）版的優點是程式碼直接對應數學定義 F(n)=F(n-1)+F(n-2)，可讀性高、易於驗證正確性；缺點是會重複計算大量重疊子問題（overlapping subproblems），時間複雜度達 O(2^n)，且遞迴深度 O(n) 佔用堆疊，n 大時有堆疊溢位（stack overflow）風險，函式呼叫亦有額外開銷。 四、迭代（iterative）版以兩個變數保存 F(n-1)、F(n-2)，迴圈由 2 到 n 逐項累加，時間 O(n)、空間 O(1)，無堆疊溢位與呼叫開銷，執行效率明顯較佳；缺點是程式較不直觀，需自行維護變數更新順序（須先暫存舊值再更新），邊界條件 n=0、n=1 要特別處理，除錯也較不口語化。 五、改進建議：遞迴版可加入記憶化（memoization）或動態規劃（dynamic programming），把時間降為 O(n)；講求效能時可用矩陣快速冪（matrix exponentiation）達 O(log n)，或以 Binet 公式配合浮點運算。兩種寫法在大 n 時都會面臨整數溢位，須改用大數（big integer）或取模運算。
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, Exclusive OR）的真值表為 00→0、01→1、10→1、11→0，即「相異輸出 1」。其正規式（canonical SOP）為 F = A'B + AB'，其中 A'、B' 為 NOT 閘的輸出。此式僅含 AND、OR、NOT 三種運算，正好符合題目限制，不需使用 NAND 或 XOR 閘。 二、電路結構描述（請考生依此繪製）：左側為輸入 A、B。A 分接至一個 NOT 閘得 A'，B 分接至另一個 NOT 閘得 B'。第一個 AND 閘輸入接 A' 與 B，輸出 X1；第二個 AND 閘輸入接 A 與 B'，輸出 X2；最右側 OR 閘輸入接 X1、X2，輸出即 F = A XOR B。圖上須標示各閘名稱、輸入腳與節點代號。 三、相等（EQUAL）電路判斷 A 是否等於 B，真值表為 00→1、01→0、10→0、11→1，即同或（XNOR, Exclusive NOR）。其布林式為 F = A'B' + AB，同樣只用到 AND、OR、NOT。直觀意義是「同為 0」或「同為 1」兩種情形皆輸出 1，其餘輸出 0。 四、電路結構描述：輸入 A、B 分別經 NOT 閘產生 A'、B'。第一個 AND 閘接 A'、B'，輸出 X1（代表兩者皆 0）；第二個 AND 閘接 A、B，輸出 X2（代表兩者皆 1）；OR 閘接收 X1、X2，輸出 F。因 XNOR 為 XOR 的反相，亦可先畫 XOR 電路再串接一個 NOT 閘，閘數相同但層數增加一級。 五、比較與注意事項：兩電路共用同一組反相器，XOR 與 XNOR 互為補數，實作時可共用 A'、B' 節點以減少閘數；AND、OR 閘的 fan-in（扇入）以 2 為宜，若庫存僅有 2 輸入閘則需串接。答題時務必畫出真值表、標明輸入輸出腳位，並以 De Morgan 定律驗證化簡結果是否等效。
在多執行緒（multithread）的作業系統，可能會有飢餓（starvation）或死
結（deadlock）的問題，請問它們各自是怎樣的情況會造成這樣的問題。
請各提出一個解決的方法，並說明為何可以解決問題。（20 分）
參考解答（AI 生成，非官方） 一、死結（deadlock）指一組執行緒互相等待對方持有的資源，若無外力介入則永遠無法前進。形成須同時滿足四項 Coffman 條件：互斥（mutual exclusion）、持有並等待（hold and wait）、不可搶佔（no preemption）、循環等待（circular wait）。例如執行緒 T1 持有鎖 A 等待鎖 B，T2 持有鎖 B 等待鎖 A，即構成循環。 二、解法一為資源全序法（resource ordering）。為每項資源編號，規定所有執行緒必須依編號遞增順序申請，則不可能出現「大編號等小編號、小編號等大編號」的環，直接破壞循環等待條件，死結因此不可能發生。另可用銀行家演算法（Banker's algorithm）於配置前檢查是否處於安全狀態（safe state），或建立資源配置圖偵測環並回滾（rollback）犧牲者。 三、飢餓（starvation）又稱無限延遲（indefinite blocking），指某執行緒雖未被死結卡住、系統仍持續運作，但其請求長期被忽略而無法獲得資源。常見於優先權排程下低優先權者永遠搶不到 CPU、最短工作優先（SJF）使長工作不斷被插隊、讀者優先的讀寫鎖使寫者久候，以及非公平鎖（unfair lock）下的競爭失利。 四、解法為老化（aging）。隨等待時間增加逐步提升該執行緒的優先權，或改用公平佇列（fair queue）、票券鎖（ticket lock）、讀寫鎖的公平模式，並設定最大等待時間後強制提升。因為等待越久優先權越高，終會高於新進者而取得資源，滿足有限等待（bounded waiting）的要求，飢餓即被消除。 五、比較與實務：死結是「環狀互等、無人能動」，屬安全性（safety）問題；飢餓是「能動但輪不到」，屬活性（liveness）與公平性問題。實務上以 lock ordering、tryLock 加逾時、避免巢狀鎖來防死結；以 aging、公平鎖與避免無上限優先權反轉來防飢餓。答題須寫出成因、對應解法與其所破壞的條件，方能得分。
請將下列中序式（infix）的表示式，轉成前序式（prefix）。（10 分）
5 + 8 * (7 – 3) + 6
下列兩個IP，根據它的遮罩，請判定是否屬於同一個子網路（subnet）？
（10 分）
200.188.170.82/27 與200.188.170.114/27
參考解答（AI 生成，非官方） 一、前序式（prefix，又稱波蘭表示法 Polish notation）將運算子置於運算元之前。轉換時先依優先權與結合性把中序式完整括號化：((5 + (8 * (7 - 3))) + 6)。再自最內層括號逐層把運算子搬到該子式最前面，即可得到前序式。 二、由內而外：7 - 3 → - 7 3；8 * (7 - 3) → * 8 - 7 3；5 + 該式 → + 5 * 8 - 7 3；最後 + 6 → 結果為 + + 5 * 8 - 7 3 6。驗證：由右往左掃描並以堆疊求值，3、7 取出做減得 4，8 乘 4 得 32，5 加 32 得 37，再加 6 得 43，與中序計算 5 + 8 * 4 + 6 = 43 一致。 三、/27 表示網路遮罩為 255.255.255.224，二進位前 27 位為 1，主機位剩 5 位，每塊大小為 2^5 = 32，可用主機數 30（扣除網路位址與廣播位址）。子網路邊界依序為 .0、.32、.64、.96、.128、.160、.192、.224。 四、將第四位元組化為二進位並與遮罩 1110 0000 做 AND：82 = 0101 0010，AND 後為 0100 0000 = 64，故所屬子網路為 200.188.170.64/27，廣播位址 .95，可用範圍 .65～.94。114 = 0111 0010，AND 後為 0110 0000 = 96，子網路為 200.188.170.96/27，廣播 .127，可用範圍 .97～.126。 五、結論：兩者網路位址分別為 .64 與 .96，並不相同，故不屬於同一個子網路，須經由路由器（router）轉送才能互通。另可注意兩者的主機位皆為 18（82-64、114-96），僅網路位不同，是常見的陷阱；判斷時務必以網路位址（network address）而非主機位數值比較。