108年 - 108 地方特考_資訊處理_三等：資料結構#81362

科目：公職◆資料結構 | 年份：108年 | 選擇題數：0 | 申論題數：12

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (12)

(一) for (int i = 0; i * i ＜ n; i++) （5 分） S

(二) for (int i = 0; Math.sqrt (i) ＜ n; i++) （5 分） S

(三) int k = 1; （10 分） for (int i = 0; i ＜ n; i++) k *= 2; for (int i = 0; i ＜ k; i++) S

(一)用雙向鏈接串列（doubly-linked list）來實作此優先佇列，請畫出其資料結構圖。（6 分）

(二)用紅黑樹（red-black tree）來實作此優先佇列，請畫出其資料結構圖。注意: 紅節點請標示 R，例如 20R 表示其值為 20 的紅（Red）節點；黑節點則請標示 B，例如 50B 表示其值為 50 的黑（Black）節點。（7 分）

(三)用最小堆積（min heap）來實作此優先佇列，請畫出其資料儲存的陣列（array）圖。注意: 陣列索引（array index）由左向右遞增。（7 分）代號：34280 頁次：2－2

(一)請畫出對應的紅黑樹（red-black tree）。請參閱上題紅黑樹節點的標示說明。（6 分）

(二)首先，插入（insert）33；接著，刪去（delete）78。請分別畫出對應的 2-3-4 樹與紅黑樹。（14 分）

(一)由張三（CS）出發，用佇列（queue）做廣度優先搜尋（breadth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）

(二)由張三（CS）出發，用堆疊（stack）做深度優先搜尋（depth-first search）走訪所有人，請寫出走訪順序的中文人名。（10 分）

(一)間隔為 1（offset of 1）（12 分）

(二)間隔為商（quotient-offset）（8 分）請分別寫出兩個雜湊表；並在間隔為 1 的雜湊表上，標示出一次聚集（primary clustering）。 40 62 83 10 20 31 45 55 70 78 90 92