民國115年 高考三級 電子工程 計算機概論考古題

民國115年 高考三級 電子工程 計算機概論收錄考選部官方試題，共 5 題可線上瀏覽，考選部未公告本科目答案。

官方資料

題目與答案

第1題

使用筆電透過家裡或hot spot 的WiFi 上網，如果碰到卡卡的不太順的 時候，檢查相關的軟硬體或設定均沒問題，那可能會有其他什麼原 因？請列舉兩個常見的可能原因，說明為何會造成網路卡卡的，那又 分別該如何解決這些因素。（10 分） IEEE 802.11 的標準，RTS/CTS 主要解決了什麼問題？為什麼它可以 解決這個問題？請說明之。（10 分）

參考解答（AI 生成，非官方）

  • 一、同頻通道壅塞與干擾：2.4 GHz 頻段僅有 1、6、11 三個互不重疊通道（non-overlapping channel），在公寓或公共 hot spot 周邊 AP 密集，若自家 AP 與鄰居 AP 落在同一通道，CSMA/CA 的載波感測、後退（backoff）與重傳次數大幅增加，airtime 被鄰居瓜分，有效吞吐量下降，使用者即感受「卡卡」。解決方式是先以 Wi-Fi 分析工具掃描通道使用狀況，再改用 5 GHz 頻段、避開壅塞通道、把通道寬度由 80 MHz 降為 40 或 20 MHz，並關閉不使用的 SSID 與舊式 802.11b 速率。
  • 二、訊號強度不足與多路徑衰落：距離過遠、隔間牆體、金屬櫃體會造成路徑損失（path loss）與多路徑干擾，訊噪比（SNR）下降後，速率自動調適（rate adaptation）會降到較低調變階級，且封包錯誤率上升導致重傳。解決方式是縮短終端與 AP 距離、調整 AP 高度與天線方向、改用 5 GHz 或 Mesh／延長器補強覆蓋，必要時換高增益天線。
  • 三、其他常見但易被忽略的因素：筆電的省電模式（power save）會週期性關閉無線網卡，造成延遲抖動；背景的系統更新、雲端同步與串流會佔滿上行頻寬；同一 AP 連線終端過多會排擠 airtime；ISP 或 DNS 解析緩慢也會讓人誤以為無線有問題。可關閉省電、設定 QoS 與流量限制、錯開更新時段、改用較快的 DNS。
  • 四、RTS/CTS 主要解決「隱藏節點問題」（hidden node problem）：802.11 以 CSMA/CA 競爭媒介，但當 A、C 兩端彼此聽不到、卻都能聽到中間的 AP B 時，兩者可能同時發送而在 B 端碰撞，且發送端因聽不到對方而無法察覺。RTS/CTS 讓傳送端先送短的 RTS（Request to Send），接收端回 CTS（Clear to Send）後才傳資料。
  • 五、為何能解決：CTS 是由接收端發出，凡是能收到 CTS 的隱藏節點都會讀取其 duration 欄位並設定網路配置向量（NAV，Network Allocation Vector），在保留期間延後發送，等於由接收端代替發送端「廣播保留」媒介，碰撞因而大幅減少，亦兼可緩解暴露節點（exposed node）問題。代價是多出控制訊框負擔，故實務上以 RTS 門檻值（RTS threshold）選擇性啟動。

第2題

請問下列的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，每回合取出 key = arr[i]，內層 while 將所有大於 key 的元素逐一右移一格，最後把 key 放入 arr[j+1]，正是「前段已排序、逐筆插入」的典型結構。
  • 二、判定理由與性質：程式中以 arr[j] > key 作為搬移條件，且只在嚴格大於時搬移，故相等元素不會互換，屬穩定排序（stable sort）；全程只使用常數個額外變數，屬原地排序（in-place）。最佳情況為輸入已排序時，內層不執行，時間複雜度 O(n)；最差與平均為 O(n^2)，適用於資料量小或近乎排序的資料。
  • 三、與其他排序的區別：氣泡排序（Bubble Sort）是相鄰兩兩交換、每回合把最大值推到尾端；選擇排序（Selection Sort）是每回合在未排序區找最小值再與前端交換；合併排序（Merge Sort）需額外陣列與遞迴分割。本題沒有相鄰交換、沒有找最小值、也沒有遞迴，故可排除。
  • 四、遞迴方式計算費氏數列：優點是程式碼直接對應 F(n)=F(n−1)+F(n−2) 的數學定義，簡潔易讀、易驗證正確性；缺點是未加記憶化（memoization）時，同一子問題被重複計算，時間複雜度達 O(2^n)，且遞迴深度為 n，n 較大時會造成堆疊溢位（stack overflow），每次函式呼叫亦有額外開銷。
  • 五、迭代方式：以兩個變數滾動保存 F(n−2)、F(n−1)，時間複雜度 O(n)、空間 O(1)，無堆疊溢位風險、執行效率高；缺點是程式較不直觀，需自行處理 n=0、n=1 的邊界條件，且若日後要改求其他遞迴式，改寫成本較高。
  • 六、建議：實務上可採迭代法，或採遞迴搭配記憶化（即動態規劃，Dynamic Programming），將時間降為 O(n)；若語言支援，也可使用尾遞迴（tail recursion）讓編譯器優化。考生作答時應明確寫出兩者的時間、空間複雜度對照，以顯示層次。

第3題

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）真值表為 (0,0)→0、(0,1)→1、(1,0)→1、(1,1)→0，即相同輸出 0、相異輸出 1。其正規式為 F = A'B + AB'，其中 A' 表示 NOT A，此式即為標準的積之和（SOP，Sum of Products）形式。
  • 二、電路結構：先以兩個 NOT 閘產生 A' 與 B'；再以一個 AND 閘產生 A'B（第一乘積項）、另一個 AND 閘產生 AB'（第二乘積項）；最後以一個 OR 閘將兩項相加輸出 F。總計使用 2 個 NOT、2 個 AND、1 個 OR，共 5 個閘，符合僅用 AND、OR、NOT 的限制。
  • 三、EQUAL 的定義與布林式：相等線路（EQUAL）判斷 A=B，真值表為 (0,0)→1、(0,1)→0、(1,0)→0、(1,1)→1，其正規式為 F = AB + A'B'，亦即同或閘（XNOR，Exclusive NOR）。最簡實作即為前述 XOR 輸出再接一個 NOT 閘，或以兩個 AND 加一個 OR 直接實現。
  • 四、繪圖說明（請考生依下列描述自行繪製）：左側畫輸入端 A、B；A 向上分岔一路接 NOT 得 A'，B 向下分岔一路接 NOT 得 B'；畫兩個 AND 閘，上者輸入接 A 與 B'，下者輸入接 A' 與 B；兩 AND 輸出匯入一個 OR 閘，OR 輸出標註 F（XOR）。EQUAL 圖則在 OR 輸出後再加一個 NOT 閘，輸出標註 F（EQUAL），並在圖旁附上四列真值表核對。
  • 五、驗證與提醒：以 A=0、B=1 代入，A'B=1、AB'=0，OR 後為 1，符合相異輸出 1；再代入 A=1、B=1，兩項皆 0，輸出 0，符合相同輸出 0。EQUAL 於 (0,0) 得 A'B'=1，於 (1,1) 得 AB=1，其餘為 0。作答時務必標示閘名稱、接線與真值表，避免只寫布林式而失分。

第4題

在多執行緒（multithread）的作業系統，可能會有飢餓（starvation）或死 結（deadlock）的問題，請問它們各自是怎樣的情況會造成這樣的問題。 請各提出一個解決的方法，並說明為何可以解決問題。（20 分）

參考解答（AI 生成，非官方）

  • 一、飢餓（Starvation）的成因：又稱無限延遲（indefinite blocking），指某個行程雖未被死結卡住，卻因排程或資源分配不公平而長期得不到 CPU 或資源。常見於優先權排程（priority scheduling）下低優先權行程永遠被高優先權搶先、最短工作優先（SJF）下長工作不斷被短工作插隊、或讀寫鎖（reader-writer lock）中寫者被源源不絕的讀者餓死。
  • 二、飢餓的解決方法：採用老化（aging）機制，讓等待越久的行程優先權逐步提升，最終必然能取得資源；或在排程器中設定公平佇列（fair queueing）、保證每個行程的最低服務比例。之所以有效，是因為它把「等待時間」轉化為可累積的優勢，打破高優先權永遠勝出的不公平結構，使任何行程的等待時間有上限。
  • 三、死結（Deadlock）的成因：指兩個以上行程互相持有對方所需的資源並等待對方釋放，形成循環等待而永無進展。發生需同時滿足四項必要條件（Coffman conditions）：互斥（mutual exclusion）、持有並等待（hold and wait）、不可搶占（no preemption）、循環等待（circular wait）。例如執行緒 T1 持有鎖 L1 等 L2，T2 持有 L2 等 L1。
  • 四、死結的解決方法：可採預防、避免、偵測與復原三種層次。最實用的是「資源排序法」——為所有鎖編號，規定只能依固定順序取得鎖，如此循環等待不可能形成，直接破壞四條件之一；亦可採銀行家演算法（Banker's algorithm）在分配前檢查是否處於安全狀態（safe state），或定期偵測後以回滾、強制釋放資源復原。
  • 五、比較與建議：老化只調整優先順序，成本低但需注意即時系統的優先權語意；鎖排序屬靜態規範，實作簡單且無執行期負擔，但需全域遵守；銀行家演算法需事先知道最大需求，實務彈性較差。考生宜點出「飢餓是公平性問題、死結是進度問題」，兩者成因與對策層次不同，避免混為一談。

第5題

請將下列中序式（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)；再據此建立運算式樹（expression tree），根為最外層的 +，左子樹為 5 + (8 * (7 − 3))，右子樹為 6；最後以前序走訪（preorder：根→左→右）讀出即得前序式。
  • 二、轉換結果：5 + 8 * (7 – 3) + 6 的前序式（prefix，即波蘭表示法 Polish notation）為：+ + 5 * 8 − 7 3 6。其中 7 − 3 先轉為 − 7 3，8 * (7−3) 轉為 * 8 − 7 3，最內層 5 加該結果轉為 + 5 * 8 − 7 3，最後再與 6 相加。
  • 三、驗證方式：以前序式由右至左掃描並用堆疊求值，或直接由運算式樹確認根節點為最後一個 +、其左子節點為 +、右子節點為 6，層次與原式一致；亦可還原為中序 ((5+(8*(7−3)))+6) 檢驗是否與原式等價。提醒考生書寫時運算子與運算元間以空格分隔，以免混淆。
  • 四、子網路的判定原則：/27 表示網路遮罩為 255.255.255.224，主機位元剩 5 位，每個子網路區塊大小（block size）為 2^5 = 32，因此子網路邊界落在 .0、.32、.64、.96、.128、.160、.192、.224。判定兩 IP 是否同子網路，即比較其位址與遮罩做 AND 運算後的網路位址是否相同。
  • 五、計算與結論：200.188.170.82 落在 64～95 區段，網路位址為 200.188.170.64/27，廣播位址 200.188.170.95；200.188.170.114 落在 96～127 區段，網路位址為 200.188.170.96/27，廣播位址 200.188.170.127。兩者網路位址不同，故不屬於同一個子網路，需經由路由器（router）轉送才能互通。