計算機概論 申論題歷屆試題與參考架構
二等考試，民國 103～115 年共 6 份試卷、30 題，其中 23 題附參考答題架構。考這一科的類科：一般警察・刑事警察人員犯罪分析組。本頁列出歷年全部題目，參考架構只列開頭的「破題」，完整的答題架構、關鍵字與作答提醒請到站內查看。
115 年（考試時間 120 分鐘） 原卷 PDF
- 1
物件導向程式設計中的封裝（encapsulation）為何意？試述之。（20 分）
（20 分）
參考架構・破題
封裝是物件導向的核心特性之一，指將資料（屬性）與操作資料的方法綁在同一個類別中，並隱藏內部實作細節，只透過公開介面與外界互動。作答方向：先下定義，再說明機制、好處，最後用程式例子佐證。
完整答題架構與關鍵字：到站內看全文
- 2
電腦中的儲存系統有那些種類？試述之。（20 分）
（20 分）
- 3
使用陣列（array）和單向鏈結串列（singly linked list）來儲存資料，各有什麼優缺點？試述之。（20 分）
（20 分）
參考架構・破題
陣列與單向鏈結串列是兩種基本線性資料結構，差異在記憶體配置方式：陣列使用連續空間，鏈結串列以節點與指標串接。作答方向：先簡述兩者結構，再從存取、插入刪除、記憶體使用等面向比較，最後說明適用情境。
完整答題架構與關鍵字：到站內看全文
- 4
請說明何謂電腦作業系統中的死結（deadlock）？死結發生的必要條件有那些？（20 分）
（20 分）
參考架構・破題
死結是指一組行程（process）彼此持有對方所需的資源，並無限期等待對方釋放，導致全部都無法繼續執行。作答方向：先定義並舉例，再完整列出四個必要條件，最後補充處理策略。
完整答題架構與關鍵字：到站內看全文
- 5
下列 C 語言程式的執行結果為何？請詳細敘述執行過程。（20 分）#include <stdio.h> void foo1(int* xp, int* yp){ int temp = *xp; *xp = *yp; *yp = temp; } void foo2(int arr[], int size){ int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n"); } void foo3(int arr[], int n){ int i, j, swapped; for (i = 0; i < n - 1; i++) { swapped = 0; for (j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { foo1(&arr[j], &arr[j + 1]); swapped = 1; } } if (swapped == 0) break; foo2(arr, n); } } int main(){ int arr[] = {47, 98, 27, 33, 7, 23, 5, 58}; int n = sizeof(arr) / sizeof(arr[0]); foo3(arr, n); return 0; }
（20 分）
參考架構・破題
這段程式是氣泡排序（bubble sort）：foo1 交換兩個整數，foo2 印出陣列，foo3 進行排序，且每一趟結束後若有交換就印出陣列，某趟沒有交換則提前結束。作答方向：先說明各函式作用，再逐趟追蹤陣列變化，最後寫出完整輸出。
完整答題架構與關鍵字：到站內看全文
108 年（考試時間 120 分鐘） 原卷 PDF
- 1
假設處理器執行某個程式，在沒有任何記憶體停頓（stall）時，每個指令的平均時脈數（CPI）為 2。已知資料快取（data cache）的錯失率（miss rate）為 3%，指令快取（instruction cache）的錯失率為 1%，每一次快取錯失的懲罰為 100 個時脈週期。假設有 30%的指令需要存取資料記憶體的內容，相對之下，完全沒有快取錯失的處理器效能會是有快取錯失時的多少倍？（20 分）
（20 分）
參考架構・破題
本題考快取錯失對 CPI 的影響：先算出含記憶體停頓的實際 CPI，再與理想 CPI 相比，即得效能倍數。關鍵是指令快取每個指令都會存取，資料快取只有 30% 的指令會存取。
完整答題架構與關鍵字：到站內看全文
- 2
假設可以平行執行兩個 10 × 20 整數矩陣的相加，接著還要循序執行 20次整數的相加。使用 20 個處理器的時候，相對於只使用一個處理器，可以得到多大的增速（speedup）？（20 分）
（20 分）
- 3
針對下列的組合語言程式sub $3, $4, $5 //暫存器 3 = 暫存器 4 - 暫存器 5 sub $1, $2, $3說明：（一）有或沒有管線危害（pipelining hazard）的理由。如果有，可能是那一種危害？（10 分）（二）是否可以利用什麼硬體的方法加速？是否可能完全避免管線的停頓（stall）？（10 分）
（20 分）
參考架構・破題
兩道指令之間存在讀後寫（RAW）資料相依：第二道 sub 要讀 $3，而 $3 由第一道 sub 寫入，因此在五級管線中會產生資料危害；可用前饋（forwarding）硬體解決，且 ALU 指令之間的相依可完全消除停頓。
完整答題架構與關鍵字：到站內看全文
- 4
針對 Quicksort 演算法：（一）請敘述如何用遞迴的方式來製作（10 分），並且（二）說明它的優點和缺點。請涵蓋時間複雜度，以及在什麼情況下會有很差的效能。 （10 分）
（20 分）
參考架構・破題
Quicksort 是分治法（divide and conquer）排序：選樞紐（pivot）分割後遞迴排序左右兩段。作答要寫出遞迴程式或虛擬碼，再分析平均、最佳、最差時間複雜度與優缺點。
完整答題架構與關鍵字：到站內看全文
- 5
TN 代表一個程式在輸入資料的個數為 N 時的執行時間。已知：T1 = 1 TN = TN-1 + N, N >= 2請逐步推導出該程式的時間複雜度。（20 分）
（20 分）
本題含圖表或公式，請對照原卷 PDF。
107 年（考試時間 120 分鐘） 原卷 PDF
- 1
下圖是使用 Cache 裝置的電腦內部示意圖：
（一）請將 Registers、Cache、Memory 這三種資料儲存裝置的存取速度，由慢至快列出來。（4 分）
（二）有人說過“Cache memory is so efficient despite its small size. The answer is due to the 80-20 rule.”，請說明何謂 80-20 rule？（4 分）
（三）為何 Cache memory 會讓電腦的計算比較有效率？（4 分）
（四）上圖 Control Unit 中有一個裝置：PC。請說明 PC 的主要用途為何？（4 分）
（五）上圖 Control Unit 中有一個裝置：IR。請說明 IR 的主要用途為何？（4 分）（請接第二頁）107年公務人員特種考試警察人員、一般警察人員考試及 全三頁107年特 種 考 試 交 通 事 業 鐵 路 人 員 考 試 試 題 第二頁考 試 別：一般警察人員考試等 別：二等考試類 科 別：刑事警察人員犯罪分析組
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 2
下圖是一般電腦其程式（Program）、工作（Job）、程序（Process）之間的狀態轉移圖。
（一）請問“Ready”和“Running”的狀態有何差別？（4 分）
（二）圖中有一句話“Time slot exhausted”，通常一個 time slot 是多久？（請寫“介於 1天至 1 小時”、“介於 1 小時至 1 分鐘”、“介於 1 分鐘至 1 秒鐘”或“少於 1秒鐘”） 。（4 分）
（三）圖中有一句話“an interrupt occurred”，請舉出一個會發生 interrupt 的例子。（4 分）
（四）請問這個系統是否屬於 time sharing 的系統？說明理由。 （4 分）
（五）這個系統有可能會發生 deadlock，請說明理由。 （4 分）（請接第三頁）107年公務人員特種考試警察人員、一般警察人員考試及 全三頁107年特 種 考 試 交 通 事 業 鐵 路 人 員 考 試 試 題 第三頁考 試 別：一般警察人員考試等 別：二等考試類 科 別：刑事警察人員犯罪分析組
（20 分）
本題含圖表或公式，請對照原卷 PDF。
- 3
下面為一以 C 語言撰寫之副程式，用來解決河內塔（tower of Hanoi）問題。void tower(int n, char start, char tmp, char end) { if (n==1) { printf("Move disk %d from %c to %c\n", n, start, end); return; } tower(n-1, start, end, tmp); printf("Move disk %d from %c to %c\n", n, start, end); tower(n-1, tmp, start, end); }
（一）何謂河內塔（tower of Hanoi）問題？（4 分）
（二）如果主程式呼叫 tower(2, 'A', 'B', 'C')，請問輸出是什麼？（4 分）
（三）如果主程式呼叫 tower(8, 'A', 'B', 'C')，請問輸出總共會有多少行？（4 分）
（四）上面 tower 副程式中的“if (n==1)”如果改成“if (n==0)”，並且主程式呼叫tower(8, 'A', 'B', 'C')，請問輸出總共會有多少行？（4 分）
（五）上面 tower 副程式屬於遞迴副程式（recursive subroutine）。另有一種型態稱為coroutine，請說明 recursive subroutine 和 coroutine 有何差別？（4 分）
（20 分）
參考架構・破題
本題以河內塔考遞迴的追蹤、遞迴關係式求解，以及 subroutine 與 coroutine 的差異。關鍵在建立輸出行數的遞迴式 T(n)=2T(n-1)+1。
完整答題架構與關鍵字：到站內看全文
- 4
我 們 有 各 式 各 樣 的 問 題 想 使 用 電 腦 來 解 決 。 而 問 題 依 計 算 的 複 雜 度 可 分 類 為polynomial-time solvable、NP-complete、unsolvable 等類別。
（一）請問 travelling salesperson problem 是否屬於 NP-complete？（4 分）
（二）請問 travelling salesperson problem 是否屬於 polynomial-time solvable？（4 分）
（三）請問 halting problem 是屬於其中那個類別？（4 分）
（四）請問 minimum spanning tree problem 是屬於其中那個類別？（4 分）
（五）為了表達計算的複雜度，我們常使用 big-O notation 來表示一個演算法或程式的效能。何謂 big-O notation？（4 分）
（20 分）
參考架構・破題
本題考計算理論的複雜度分類：P、NP-complete 與不可解問題，並以 TSP、停機問題、最小生成樹為例，最後定義 big-O。作答要先界定類別定義，再逐一歸類並說明理由。
完整答題架構與關鍵字：到站內看全文
- 5
請回答下列有關單位的問題。
（一）有一台雷射印表機解析度是 1200 DPI，請寫出 DPI 的英文全名，並說明 1200 DPI其意義為何？（4 分）
（二）有一台雷射印表機速度是 18 PPM，請寫出 PPM 的英文全名，並說明 18 PPM 其意義為何？（4 分）
（三）有一支手機螢幕的解析度是 458 PPI，請寫出 PPI 的英文全名，並說明 458 PPI 其意義為何？（4 分）
（四）有一支手機其相機為 1200 萬像素，請問 1200 萬像素其意義為何？（4 分）
（五）有一顆 CPU 速度是 49360 MIPS，請寫出 MIPS 的英文全名，並說明 49360 MIPS其意義為何？（4 分）
（20 分）
106 年（考試時間 120 分鐘） 原卷 PDF
- 1
請使用 C 語言利用環狀陣列（Circular Array）實做ㄧ佇列（Queue）。給予如下定義：#define MAX_Q 100; /* Arbitrary size of the queue */ typedef int ITEM_TYPE; typedef struct q_type { ITEM_TYPE item[MAX_Q]; int front; /* Always points to the item prior to the front */ int rear; /* Always points to the rear */ } Q_TYPE;假設ㄧ開始建立ㄧ佇列的程式如下: void create_queue ( Q_TYPE *queue) { queue -> front = 0; queue -> rear = 0; }請完成
（一）加入ㄧ資料項目至佇列的後端 (Add item to the rear of the queue.): void enqueue (Q_TYPE *queue, ITEM_TYPE new_item ) /* Preconditions: queue not full */（10 分）
（二）從佇列前端移除ㄧ資料項目 (Remove item from the front of the queue.): void dequeue (Q_TYPE *queue, ITEM_TYPE *old_item ) /* Preconditions: queue not empty */（10 分）106年公務人員特種考試警察人員、一般警察人員考試及106年特種考試交通事業鐵路 代號：20240全一張考 試 別：一般警察人員考試等 別：二等考試類 科 別：刑事警察人員犯罪分析組
（20 分）
參考架構・破題
本題考環狀陣列佇列的實作。依題目定義 front 指向「第一個元素的前一格」、rear 指向最後一個元素，初始 front＝rear＝0；入列與出列都以取餘數 % MAX_Q 讓索引繞回，形成環狀。
完整答題架構與關鍵字：到站內看全文
- 2
給予如下的 2-3 tree：
（一）畫出連續加入資料 37 與 36 後的 2-3 tree。（10 分）
（二）從給予的 2-3 tree，畫出連續刪除資料 70, 100, 與 80 後的 2-3 tree。（10 分）
（20 分）
- 3
給予依序如下資料 40, 20, 60, 10, 30, 50, 70：
（一）將此串資料建成二元搜尋樹（Binary Search Tree）。（10 分）
（二）承題（一），執行二元樹的何種運算，可將此串資料做排序？（10 分）
（20 分）
- 4
給予ㄧ鏈結串列（Linked List）的節點（Node）定義如下： （20 分）struct node { int info; struct node *next; }; typedef struct node *NODEPTR;請用 C 語言寫ㄧ函數 concat (NODEPTR *plist1, NODEPTR *plist2)，將 plist2 鏈結串列接在鏈結串列 plist1 的後面，plist1 與 plist2 分別各是ㄧ環狀鏈結串列（Circular Linked List）之指標，plist1 與 plist2 指標分別指在各環狀鏈結串列的最後一個節點。
（20 分）
參考架構・破題
本題考環狀鏈結串列的串接。關鍵在於指標指向最後一個節點，因此 last->next 就是第一個節點，只要調整兩個 next 指標與一個串列指標即可在 O(1) 完成，不需走訪。
完整答題架構與關鍵字：到站內看全文
- 5
看ㄧ快取記憶體設計能否進一步改善，我們要瞭解快取記憶體失誤的種類（Types of，請列舉三類快取記憶體的失誤（Three Types of Cache Misses）Misses） ，並請說明。（20 分）
（20 分）
參考架構・破題
快取錯失依成因可分為三類，即 3C 模型：強制性錯失（Compulsory）、容量錯失（Capacity）、衝突錯失（Conflict）。作答要逐類寫出定義、發生原因與改善方法，並說明各方法的副作用。
完整答題架構與關鍵字：到站內看全文
104 年（考試時間 120 分鐘） 原卷 PDF
- 1
何謂機器週期（machine cycle）？試詳述執行一條指令的步驟。（10 分）
（10 分）
- 2
請就下列左右兩個圖示架構，分別說明是屬於何種多處理器架構？並比較其優缺點。（10 分）處理器 處理器 處理器 處理器 處理器 處理器快取 快取 快取 快取 快取 快取連結網路 記憶體 記憶體 記憶體記憶體 I/O 連結網路
（10 分）
本題含圖表或公式，請對照原卷 PDF。
- 3
目前國內網購貨款的主要支付方式有：刷信用卡，到 ATM 或金融機構匯款，到超商付款，面交，貨到付款等五種方式。去年因服貿協定，引起非常熱門議題是網購的第三方支付模式，請問何謂第三方支付模式？第三方支付模式對網購有何影響？（20 分）
（20 分）
- 4
下列 C 語言函數是氣泡排序演算法void ourBubbleSort (int *iArray, int n) { for (int i =0; i<n-1; i++) for (int j = i+1; j<n; j++) if (iArray[i]>iArray[j]) { int iTemp = iArray[i]; iArray[i] = iArray[j]; iArray[j] = iTemp;} }
（一）請問其時間複雜度為何？（5 分）
（二）若 iArray 陣列的內容都在 0～9 的範圍內，共有 n 筆，請寫出計數排序（counting sort）演算法。（15 分）
（三）承（二），請問計數排序法的時間複雜度和空間複雜度為何？（10 分）104年公務人員特種考試警察人員、一般警察人員考試及104年 全一張等 別： 二等一般警察人員考試類 科 別： 刑事警察人員犯罪分析組
（30 分）
參考架構・破題
第一小題分析題目給的雙層迴圈交換排序；第二、三小題利用值域只有 0～9 的特性，用計數排序達到線性時間，重點在寫出正確的 C 程式並分清楚時間與空間複雜度。
完整答題架構與關鍵字：到站內看全文
- 5
網路的資訊安全是重要的議題，資訊傳遞須加以編碼，以避免被竊取，簡單易用的公有鍵（Public Key）編碼方法說明如下：設公有鍵為一對（e,d）可逆轉乘式（multiplicative inverses），若原文為 p、密文為 c、模組數為 m，編碼方式為 c = p × e mod m；解碼方式為 p = c × d mod m。
（一）若模組數 m=67，公有鍵（Public Key）為（30,38），原文數列為 1、3、5，請問編碼後的密文數列為何？（6 分）
（二）承（一），若密文數列為 60、53，請問原文數列為何？（4 分）
（三）承（一），以 C 語言撰寫的主函數如下：#include <stdio.h> #include <stdlib.h> const int m=67, n=3; int main() { int iTestArray[n]={1,3,5};//測試資料int c, p, e=30, d=38; int encode(int p,int e); //原型宣告int decode(int c,int d); //原型宣告for (int i=0; i<n; i++) { c= ; p= ; printf(“%d %d\n”, c, p); } system(“pause”); return 0; }請以 C 語言完成其編碼函數 encode()、解碼函數 decode()和主函數虛線部分。（20 分）
（30 分）
103 年（考試時間 120 分鐘） 原卷 PDF
- 1
在計算機內部表達 single precision（單精確度）的實數，一般都採用 IEEE 754 standards，使用 32 個位元，格式如下：（每小題 5 分，共 10 分）
（一）請問實數 2.875 用此表示法時 32 個位元的內容為何？
（二）在計算機內部表達 double precision（雙精確度）的實數，一般也都採用 IEEE 754 standards，請問此時會使用幾個位元？
（10 分）
參考架構・破題
本題考 IEEE 754 浮點數表示法：先把 2.875 轉二進位並正規化，再依符號、指數（偏差 127）、尾數三欄填入 32 位元；第二小題答雙精確度的位元數與欄位配置。
完整答題架構與關鍵字：到站內看全文
- 2
以下為一個以 C 語言撰寫之程式。（每小題 5 分，共 15 分）#include <stdio.h> #include <stdlib.h> int test(int a, int b); int main(void){ int a, b; printf("請輸入 a 和 b: "); scanf("%d%d", &a, &b); printf( "%d\n", test(a, b)); system("pause"); return 0; } /* end main */ int test(int a, int b) { if (a % b == 0) { return b; } else { return test(b, a % b); } } /* end function test */
（一）請問 test 這個函數的功能為何？
（二）當該程式執行時，若輸入的 a 及 b 值分別為 52 及 40，請問其執行結果為何？
（三）當該程式執行時，若輸入的 a 及 b 值分別為 52 及 0，請問其執行結果為何？103年 公 務 人 員 特 種 考 試 警 察 人 員 考 試103年 公 務 人 員 特 種 考 試 一 般 警 察 人 員 考 試 全一張103年 特 種 考 試 交 通 事 業 鐵 路 人 員 考 試 試 題 （背面）等 別：二等一般警察人員考試
（15 分）
- 3
當 CPU 要和輸出入裝置同步時，有三種方式：⑴programmed I/O；⑵interrupt- driven I/O；⑶DMA。（每小題 5 分，共 25 分）
（一）請問一般而言，那一種方式最浪費 CPU 的計算能量？為什麼？
（二）請問對大量且具規則性的資料作輸出入時，那一種方式效率最高？為什麼？
（三）請問 CPU 需要和輸出入裝置同步的原因主要有那些？
（四）請寫出 DMA 的英文全名。
（五）請說明 interrupt-driven I/O 的工作方式。
（25 分）
- 4
給定一個有權重的圖（weighted graph）G 如下，相異節點之間如果沒有 edge，則設定其權重為∞；而節點至自身節點的權重則設定為 0。（每小題 5 分，共 25 分）
（一）請繪出其 adjacency matrix。
（二）請列出其 adjacency lists。
（三）請找出其一種 minimum spanning tree，並繪圖表示之。
（四）令節點 A 為根節點（root），請列出做 breadth-first traversal 的一種可能結果。
（五）請寫出 G 中 traveling salesperson problem 的解答（含其路徑及總成本）。
（25 分）
- 5
遞迴演算法（recursive algorithm）經常被用來解決某些問題。（每小題 5 分，共 25 分）
（一）何謂遞迴演算法？
（二）二分搜尋法（binary search）是否屬於遞迴演算法？請說明其理由。
（三）利用二分搜尋法（binary search）在 2030 筆資料中搜尋某一特定資料時，最多會對幾筆資料做比對？
（四）遞迴演算法的另一個典型範例是 Hoare 在 1962 年提出的一個排序演算法，請問這個演算法的名稱為何？
（五）動態規劃法（dynamic programming）也經常被用來解決某些問題。請問它和遞迴演算法（recursive algorithm）主要的差異為何？
（25 分）
其他等別的「計算機概論」
- 計算機概論（高考三級）（70 題）
- 計算機概論（地方特考三等）（69 題）
題目來源：考選部考畢試題查詢平臺（政府資訊公開資料）；參考架構為本站自撰，僅供準備方向參考，非官方標準答案。最後更新：。