刑事警察人員 106 年計算機概論考古題

請使用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年特種考試交通事業鐵路 人員、退除役軍人轉任公務人員考試試題 全一張 （背面） 考試別： 一般警察人員考試 等 別： 二等考試 類科別： 刑事警察人員犯罪分析組 科 目： 計算機概論（包括計算機結構、資料結構、程式設計）

給予如下的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 分）