112年高考三級資料結構第四題
四、分散式資料庫為一個分散在電腦網路的許多在邏輯上相關資料庫的集合，請畫出分散式資料庫系統三層主從伺服器架構 (Three-tier Client-server Architecture)，並論述其運作原理，分散資料的管理具有不同層次 (Levels) 的透明度 (Transparency)，請論述三種透明度及相關技術。（25分）
- 7月 19 週三 202323:51
112年高考三級資料結構第四題
112年高考三級資料結構第四題
- 12月 22 週四 202200:14
111年地方特考三等資料結構第四題
111年地方特考三等資料結構
四、二元堆積 (Binary Heap) 是一種優先佇列 (Priority Queue)，主要用來管理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或前後順序的鍵值 (Key)，我們在此假設鍵值越低的資料物件有越高的優先權。
(一)請完整描述最小堆積 (Min_Heap) 的定義與相關的操作功能。（5分）
(二)請說明堆積排序 (Heap Sort) 的方法並分析其時間複雜度。（5分）
(三)若有兩個二元樹 T1 及 T2，其節點具有堆積特性且高度分別是 O(log n)與 O(log m)，請提供一個方法將此兩個二元樹結合成為一個節點具有堆積特性的二元樹 T，此方法的時間須為 O(logn+logm)。（10分）
- 10月 21 週五 202218:04
111年國家安全情報人員三等資料庫應用第一題
111年國家安全情報人員三等資料庫應用
一、一篇學術文章通常有許多屬性，包括唯一編號 (paper_ID)、論文名稱 (title)、發表期刊 (journal)、發表卷期 (vol)、發表年 (year)、起始頁 (start) 及結束頁(end)，若可對應到先前提出過的一或多篇技術報告，則另加上該技術報告編號 (TR-ID)。每一本期刊一年可出刊多次，每次都有不同的卷期 (連續但不重複)，且視論文長短，結束頁一定不會小於起始頁，且不會把兩篇論文(部分) 內容編排在同一頁。請用以下關連及資料表回答問題。
Paper (ID, title, journal, vol, year, start, end, TR-ID)
(四)下列那幾個是正確的 SQL 語法？（5分）
1.SELECT * FROM Paper WHERE end-start > 10;
2.SELECT * FROM Paper WHERE end-start < 0;
3.SELECT SUM(title) FROM Paper;
4.SELECT year, COUNT(*) FROM Paper GROUP BY year;
5.SELECT year, COUNT(*) FROM Paper ORDER BY year;
(五)下列 SQL 語法執行後會產生幾行 (tuples) 的資料？（5分）
1.SELECT paper_ID FROM Paper WHERE year <= 2022;
2.SELECT DISTINCT paper_ID FROM Paper WHERE year <= 2022;
3.SELECT AVG(year) FROM Paper GROUP BY journal;
4.SELECT * FROM Paper WHERE journal LIKE '%t';
5.SELECT title FROM Paper ORDER BY year;
- 9月 30 週五 202200:06
111年高考三級資料結構第四題
111年高考三級資料結構
四、用 G = (V, E) 表示一個無方向性圖形，其中 V 是點的集合，E 是一組節點(Vertices) 形成邊及對應權重 (Weights) 所組成的集合。今有一圖形 G = (V, E)，V = {0, 1, 2, 3, 4, 5}，圖形的邊與權重值以如下的定義儲存對應連接矩陣 (Adjacency matrix) 表示中的值
#define MAX_EDGES 100
typedef struct {
int col;
int row;
int weight;
} edge;
edge a[MAX_EDGES];
已知陣列 a 儲存對應連接矩陣相連接邊的內容如下：a = {(3, 0, 2), (4, 0, 1), (5, 0, 20), (2, 1, 7), (5, 1, 24), (3, 2, 15), (4, 2, 10), (5, 2, 25), (4, 3, 3)}。請畫出陣列 a 所儲存的圖形，然後，利用 Prim 演算法從節點0開始依加入其它節點的順序，畫出此圖之最小擴張樹 (Minimum spanning tree)，並計算其最低權重或成本值。（25分）
- 9月 29 週四 202223:59
111年高考三級資料結構第三題
111年高考三級資料結構
三、一個二元搜尋樹 (Binary search tree) 的前序追蹤 (Preorder traversal) 結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20
請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree (NODEPTR tree)，輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25分）
struct node { int info; struct node *left; struct node *right; } typedef struct node *NODEPTR; void sortTree(NODEPTR tree) { } |
- 9月 27 週二 202220:47
111年高考三級資料結構第二題
111年高考三級資料結構
二、利用鏈結串列 (Linked list) 實做佇列 (Queues)，給予如下鏈結串列節點及 佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最後一個節點，請使用 C 語言完成 insert(pq, x) 程序，將整數值 x 加入 (Insert) 到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可使用函數 getnode( ) 配置 (Allocate) 一新節點。（25分）
struct node { int info; struct node *next; }; typedef struct node *NODEPTR; struct queue { NODEPTR front, rear; }; struct queue q; NODEPTR getnode( ) { NODEPTR p; p = (NODEPTR)malloc(sizeof(struct node)); return(p); } insert(pq, x) struct queue *pq; int x; { NODEPTR p; } |
- 9月 21 週三 202218:42
111年身心障礙人員三等資料結構第二題
111年身心障礙人員三等資料結構
二、以下7個數字 [21, 1, 16, 11, 25, 9, 35]，要儲存到 Hash Table 中，Hash Table的儲存空間是一個索引從0開始的一維陣列 (Array)。假設 Hash 函數為 H(Key) = (Key*3) mod 7，裝填因子 (Load Factor) 為0.7。
(一)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的線性探測法 (Linear Probing)：增量函數 F(i) = i (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分）
(二)若處理 Hash Table 衝突的方法為開放定址法 (Open Addressing Hashing)中的平方探測法 (Quadratic Probing)：增量函數 F(i) = i2 (i 為衝突的次數)。請依序列出每存入一個數字後的 Hash Table 的內容。接著計算在相同機率的情況下，查找成功及查找失敗的平均查找長度 (Average Search Length; ASL)。（15分）
- 9月 20 週二 202216:49
111年關務三等資料結構第四題
111年關務三等資料結構
四、以文本 (text) X = “AGTCATTCGATTC”，樣式 (pattern) Y = “ATTC” 兩字串為例，請問使用暴力比較/窮舉法 (exhaustive search) 中的樣式前向法(forward) 及後向法 (backward) 各需比較幾次？（10分）
- 3月 16 週四 201714:44
105年關務三等資料結構第二題
105年關務三等資料結構
二、(一)請解釋何謂引線二元樹 (threaded binary tree) 及其優點為何。（10分）
(二)若要以鏈結串列 (linked list) 來表達引線二元樹，試設計一適當之節點結構。（5分）
(三)請畫出下圖所示二元樹之引線二元樹。請分別畫出有頭端節點 (header node) 與無頭端節點之引線二元樹。（10分）
(四)請寫出在引線二元樹中以線性時間（即時間複雜度為 O(n)）進行中序尋訪的演算法。（10分）
1
國考資訊處理解答 (7)