112年高考三級資料結構第四題
|
四、分散式資料庫為一個分散在電腦網路的許多在邏輯上相關資料庫的集合，請畫出分散式資料庫系統三層主從伺服器架構 (Three-tier Client-server Architecture)，並論述其運作原理，分散資料的管理具有不同層次 (Levels) 的透明度 (Transparency)，請論述三種透明度及相關技術。（25分） |
答：
(一)分散式資料庫系統三層主從伺服器架構
1.展示層(Presentation Tier)：客戶端(Client)
(1)個別用戶端的電腦上安裝了具備圖形化操作介面 (GUI) 的程式，而這些程式可以透過特定格式的表單，提供使用者輸入適當的資訊，並且將結果顯示出來，以便與伺服器進行互動。例如瀏覽器或其他客戶端應用程式。
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分） |
答：
(一)
1.每一個節點的鍵值必須小於它的子節點的鍵值。特性如下：
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; |
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; |
111年高考三級資料結構
|
三、一個二元搜尋樹 (Binary search tree) 的前序追蹤 (Preorder traversal) 結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20 請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree (NODEPTR tree)，輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25分）
|
111年高考三級資料結構
|
二、利用鏈結串列 (Linked list) 實做佇列 (Queues)，給予如下鏈結串列節點及 佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最後一個節點，請使用 C 語言完成 insert(pq, x) 程序，將整數值 x 加入 (Insert) 到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可使用函數 getnode( ) 配置 (Allocate) 一新節點。（25分）
|
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分） |
答：
[21, 1, 16, 11, 25, 9, 35]
裝填因子 = 資料個數/總容量 = 0.7，表示有7筆資料，總容量10個。
(一)
111年關務三等資料結構
|
四、以文本 (text) X = “AGTCATTCGATTC”，樣式 (pattern) Y = “ATTC” 兩字串為例，請問使用暴力比較/窮舉法 (exhaustive search) 中的樣式前向法(forward) 及後向法 (backward) 各需比較幾次？（10分） |
答：
暴力比較法實作：
|
#include <iostream> #include <string> using namespace std; int Find(char Text[ ], char Pattern[ ]) { |
105年關務三等資料結構
|
二、(一)請解釋何謂引線二元樹 (threaded binary tree) 及其優點為何。（10分） (二)若要以鏈結串列 (linked list) 來表達引線二元樹，試設計一適當之節點結構。（5分） (三)請畫出下圖所示二元樹之引線二元樹。請分別畫出有頭端節點 (header node) 與無頭端節點之引線二元樹。（10分） (四)請寫出在引線二元樹中以線性時間（即時間複雜度為 O(n)）進行中序尋訪的演算法。（10分） |
答：
(一)引線二元樹及其優點為何？
國考資訊處理解答 (7)
