加載中. ..
PDF
106年公務人員特種考試警察人員、一般警察
人員考試及106年特種考試交通事業鐵路
人員、退除役軍人轉任公務人員考試試題 代號：20240 全一張
（正面）
考試別： 一般警察人員考試
等別： 二等考試
類科別： 刑事警察人員犯罪分析組
科目： 計算機概論（包括計算機結構、資料結構、程式設計）
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、請使用 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 全一張
（背面）
考試別： 一般警察人員考試
等別： 二等考試
類科別： 刑事警察人員犯罪分析組
科目： 計算機概論（包括計算機結構、資料結構、程式設計）
二、給予如下的 2-3 tree：
畫出連續加入資料 37 與36 後的 2-3 tree。（10 分）
從給予的 2-3 tree，畫出連續刪除資料 70, 100, 與80 後的 2-3 tree。（10 分）
三、給予依序如下資料 40, 20, 60, 10, 30, 50, 70：
將此串資料建成二元搜尋樹（Binary Search Tree）。（10 分）
承題，執行二元樹的何種運算，可將此串資料做排序？（10 分）
四、給予ㄧ鏈結串列（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 指標分別指在各環狀鏈結串列的最後一個節點。
五、看ㄧ快取記憶體設計能否進一步改善，我們要瞭解快取記憶體失誤的種類（Types of
Misses），請列舉三類快取記憶體的失誤（Three Types of Cache Misses），並請說明。
（20 分）