國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

關務三等資料結構：106

身心障礙人員三等資料結構：無

鐵路特考高員三級資料結構：106

高考三級資料結構：106

專利商標審查人員三等資料結構：無

關務人員升官等薦任資料結構：106

資訊技師高等資料結構與資料庫及資料探勘：106

地方特考三等資料結構：106

[一○六年關務三等資料結構]

106年公務人員特種考試關務人員考試、

106年公務人員特種考試身心障礙人員考試及           代號：10460 全一頁

106年國軍上校以上軍官轉任公務人員考試試題

考 試 別：關務人員考試

等    別：三等考試

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                    座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、一個二元搜尋樹 (binary search tree) 初始為空的，依序插入 (insert) 5, 11, 9, 24, 10, 2, 15, 3。

(一)請繪出完成輸入後的二元搜尋樹。（10分）

(二)試說明如何利用一維陣列來表示 (represent) 此二元搜尋樹，並在此一維陣列中保有此樹狀結構父節點與子節點的關係性。（5分）

(三)請設計一演算法能將此二元搜尋樹，依數值由大到小的方式輸出。（5 分）

(四)對(一)產生的二元搜尋樹，刪除數值5。請繪出完成刪除動作後的二元搜尋樹。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、(一)請使用 C 或 Java 語言寫一副程式 void FindMinMax(int [ ] A, int n, int Min, int Max)，對一個未排序的 (unsorted) 且長度為 n 的陣列 A[0：n-1]，尋找陣列中的最小值及最大值，並分別存入Min 及Max，此副程式在最佳情況 (best case) 下，只花費n-1 次的數值比較運算(comparison)。（17分）

(二)請舉例說明此副程式最差情況 (worst case) 所花費的數值比較運算(comparison) 次數。（8分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、一個工廠有 n 台機器 M₁, M₂, …, M_n 及 k 份工作 J₁, J₂, …, J_k，每份工作都有其所需的執行時間 T(J₁), T(J₂), …,T(J_k)。每一台機器一次只能執行一份工作，每份工作只能交給一台機器執行，n 台機器可同時執行n 份不同的工作。

(一)請設計一個 Greedy (貪婪) 的演算法，來解決工作排程的問題，使得完成 k 份工作的時間最短。（15分）

(二)此 Greedy 演算法適合使用何種資料結構來完成？（5分）

(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、有一雜湊表格 (hash table) 包含11個桶 (buckets)，位址編號由0至10，每個桶有一個槽 (slot)。雜湊函數 h 的定義為 h(key) = key%11 (註：a%b 表示 a 除以 b 的餘數)。當有碰撞 (collision) 發生時，採用線性探測 (linear probing) 解決碰撞問題。從空的雜湊表格開始，依序加入10個整數5, 51, 23, 68, 12, 36, 6, 30, 32, 10。

(一)請繪出加入10個整數後的雜湊表格。（15分）

(二)欲在此雜湊表格中尋找資料值35，請說明須經過幾次的資料值比對，才能確定資料值35不在此雜湊表格中。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○六年鐵路特考高員三級資料結構]

106年公務人員特種考試警察人員、一般警察

人員考試及106年特種考試交通事業鐵路               代號：70770 全一張

人員、退除役軍人轉任公務人員考試試題

考 試 別：鐵路人員考試

等    別：高員三級考試

類 科 別：資訊處理

科    目：資料結構

考試時間：2小時                                    座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

一、(一)串列 (list or sequence) 是一個函數，從整數的子集合對應到另一個集合。請寫出兩個集合 s1, s2 及一個函數 f 來定義串列 [2, 2, 1, 3]。（10分）

(二)分別使用 Java ArrayList 及 Java LinkedList 來實作上述的串列，請分別畫出草圖 (sketch) 表示之 (注意：兩種資料結構的草圖上，都要註明索引 index)。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、對下面的圖 (graph)，請分別使用佇列 (queue) 及堆疊 (stack)，從 A 出發，分別進行廣度優先走訪 (breadth-first traversal) 及深度優先走訪 (depth-first traversal)，請寫出兩種走訪結果。注意：請依字母順序 (alphabetical order)處理。而且，要寫出走訪時佇列及堆疊等資料結構的內容。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、請寫出下面 m1, m2, m3, m4 四個程式的 Big O 時間估算。（20分）

public static int m1(int N) {

int x = 0;

for (int i = 0; i < N; i++)

x++;

return x;

}

public static int m2(int N) {

int x = 0;

for (int i = 0; i < N; i++)

for (int j = 0; j < i; j++)

x++;

return x;

}

public static int m3(int N) {

if (N == 0) return 0;

int x = 0;

for (int i = 0; i < N; i++)

x += m3(N-1);

return x;

}

public static int m4(int N) {

if (N == 1) return 3;

return 3+m4(N/2);

}

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、將下列資料 60, 30, 80, 20, 50, 70, 90, 40, 35

依序分別加入原本為空的紅黑樹 (red-black tree) 及2-3-4樹，請分別寫出結果。（20分）

注意：紅黑樹的紅色 (Red) 節點，請註明 R，例如：資料30 的節點是紅色的，則請寫 30R。

注意：2-3-4 樹的節點要分裂 (split) 時，最小資料放在左子節點，最大兩個資料放在右子節點，次小資料放在父節點。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、將下列資料 60, 30, 80, 20, 50, 70, 90, 40, 35

(一)依序分別加入原本為空的最小堆積 (min heap) 及空的陣列 (array) 中，請分別寫出結果，表示資料儲存的情形。（10分）

(二)承題(一)，分別自最小堆積及陣列中刪去30，刪除資料後，需重新建立最小堆積。而陣列中所有在此資料右方之資料必須向左移，不可留空白，請分別寫出結果。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○六年高考三級資料結構]

106年公務人員高等考試三級考試試題                  代號：26050 全一張

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                 座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、給定二元樹 (binary tree) 如右圖，樹高為4且共有7個節點。

(一)請寫出該樹之後序遍歷 (postorder traversal) 結果。（5分）

(二)若以陣列 A[1..15] 實作該二元樹，請列舉陣列 A[1..15] 的內容。（5分）

(三)若要將數值 x 設為或取代 A[i] (任一 1 ≦ i ≦ 7) 所代表的節點之右子節點 (right child node) 的內容，令 x 會被放入陣列中 A[j] 的位置。請以 j、i  表示，寫出 j 位置之公式。（5分）

(四)若要在原始的二元樹中加入一些節點使其成為完整二元樹 (complete binary tree) 及完滿二元樹 (full binary tree)，請問最少各需加入幾個新節點？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、遊樂園設計公司正在設計新的遊樂園，遊樂園將有9個遊樂設施，設施名稱暫定為 A, B, C, D, E, F, G, H, I。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園的初步規劃如表一，表內數字為兩遊樂設施之間商店街道之預計長度 (每條街道長度皆不同)。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決定實際建置那些商店街道。

(一)若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5分）

(二)請計算符合上述(一)小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10分）

(三)但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍9項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路 (Euler Cycle)，漢密爾頓迴路 (Hamiltonian Cycle)，旅行商人問題 (Traveling Sales Man Problem)，最短路徑 (例如 Dijkstra 演算法)，任兩點最短距離（例如弗洛伊德 (Floyd-Warshall) 演算法）？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資料已事先填入作為範例。（(a),(b),(c),(d)各5分，共20分）

表二

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定 n 個矩陣，A₁, A₂, …, A_n，且任一矩陣 A_i 大小為 p_i-1×p_i , p₀ , ..., p_n 皆為正整數。A₁×A₂×…×A_n 實際計算過程可以是 (…((A₁×A₂)×A₃)×…× An)、(A₁×(A₂×(…×(A_n-2×(A_n-1×A_n))…)))、或其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動態規劃 (dynamic programming)、二維陣列的應用及遞迴程式，可以找到最少乘法運算次數的計算順序。方法如下：令 m[i, j] 為計算 A_i×A_i+1×…× A_j 時所需最少乘法運算次數，m[i, j] 可以下列遞迴公式表示之：

(一)請說明 A₁×A₂×…×A_n 相乘過後的矩陣大小為何？（3分）

(二)透過上述方法所找到的最少乘法運算次數，應為二維陣列 m[i, j] 中的那個元素，亦即 i, j 應分別為何？（3分）

(三)若 n = 4 且 p₀ , p₁, p₂ , p₃, p₄ 分別為3, 4, 5, 4, 2，請計算並填寫出二維陣列 m[i, j]。（11分）

(四)承上小題(三)，請說明該四矩陣相乘，A₁×A₂×A₃×A₄，最少共需有幾次乘法運算。（3分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、請依序將17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21儲存至下列13桶(buckets)×1槽 (slots) 的雜湊表 (hashing table)。請以各小題所設定的雜湊函式 (hashing function) 將資料依序存入並顯示最後的雜湊表。

(一)雜湊函式 F(x) = x mod 13，碰撞時，採取「線性探測法」(open addressing with linear probing) 來放入資料。請顯示最後的雜湊表。（5分）

(二)雜湊函式F(x) = x mod 13，碰撞時，採取「二次方探測法」 (open addressing with quadratic probing) 來放入資料。請顯示最後的雜湊表。（5分）

(三)雜湊函式 F₁(x) = x mod 13，碰撞時，採取「雙探測法」 (open addressing with double hashing) 來放入資料，第二雜湊函式為 F₂(x) = 7-(x mod 7)。請顯示最後的雜湊表。（5分）

(四)若雜湊表夠大 (例如 slots = 2 或更大) 但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○六年關務人員升官等薦任資料結構]

106年公務、關務人員升官等考試、106年交通          代號：26260 全一頁

事業鐵路、公路、港務人員升資考試試題

等    級：薦任

類科（別）：資訊處理

科    目：資料結構

考試時間：2小時                                    座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、下列二維陣列為某圖 G 之相鄰矩陣 (adjacency matrix)：

(一)請列出對應同一圖 G 之相鄰串列 (adjacency list)。（5分）

(二)其最小生成樹 (minimum spanning tree) 為何？（5分）

(三)請問此圖是否為連通圖 (connected graph)？為什麼？（5分）

(四)請問此圖是否為雙連通圖 (biconnected graph)？為什麼？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、給定一字串 “she sells seashells by the seashore”：

(一)請將此字串 (包含空白字元) 用 Huffman coding 演算法編碼，並將編碼過程及結果寫出。（10分）

(二)若以字串集 {she, sells, seashells, by, the, seashore} 建立一字典樹 (trie)，請問結果為何？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、若一最大堆積 (max heap) 內部儲存下列數列：

9, 6, 8, 4, 2, 5, 7, 3, 1

請問：

(一)若插入另一數字10，請問此最大堆積內部資料依序為何？（5分）

(二)請利用(一)所得之最大堆積，以堆積排序法 (heap sort) 將其由小到大排序，並列出每回合最大堆積的結果。（10分）

(三)設計堆積排序法時，最適合的資料結構為何？為什麼？（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、考慮一數列 9, 8, 7, 6, 5, 4, 3, 2, 1：

(一)若此數列存於一維陣列中，以二元搜尋法尋找資料，經幾次比較運算可找到5？一般來說，最差情形幾次比較運算可找到？（5分）

(二)若以此數列順序，建立二元樹，所得之二元樹為何？（5分）

(三)若以此數列順序，建立三階 B 樹 (B tree of order 3)，所得之 B 樹為何？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、考慮下列的雙向圖：

(一)其相應之相鄰矩陣 (adjacency matrix) 為何？（5分）

(二)從 A 點開始，進行深度優先搜尋 (depth-first search)，所經之節點順序為何？請以字母較小節點優先輸出。（5分）

(三)若 dfs(i) 是以節點 i 出發進行深度優先搜尋的副程式，請利用 dfs(i) 寫出可判斷圖形是否連通 (connected) 的演算法，並分析其時間複雜度。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○六年資料結構與資料庫及資料探勘]

106年專門職業及技術人員高等考試

建築師、技師、第二次食品技師考試暨                 代號：01310 全一頁

普通考試不動產經紀人、記帳士考試試題

等    別：高等考試

類    科：資訊技師

科    目：資料結構與資料庫及資料探勘

考試時間：2小時                                    座號：___________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、請用相鄰矩陣 (Adjacency Matrix) 與相鄰串列法 (Adjacency List) 表示下列無向圖：（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、試寫出在二元分類問題中，評估成果的混淆矩陣 (Confusion Matrix)。判定良性腫瘤抑或是惡性腫瘤的醫療診斷中，何謂「偽陽性」(False Positive)？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、在分類決策樹中 (Decision Tree)，請舉兩個選擇分割節點 (Splitting Node) 的策略，各有何優缺點？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、假設分解綱目 R = (A, B, C, D, E) 到 S = (A, B, C) 與 T = (A, D, E)，需要有何相依性集合成立，才能證明此一分解是一個無損合併分解。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、(一)請以 SQL 語法描述，從 Student 與 Grade 兩個關聯 (Relations) 中「找出資料庫 (database) 成績超過90分的學生姓名」。（10分）

(二)該 SQL 語法的關聯代數運算式為何？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

六、給定數字串列，5, 3, 4, 1, 2。請利用 “快速排序法” 與 “氣泡排序法”，將此串列由大到小排序。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

七、何謂 NoSQL？在何類的應用中，一般 SQL 無法滿足需求？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○六年地方特考三等資料結構]

106年特種考試地方政府公務人員考試試題              代號：33680 全一張

等    別：三等考試

類    科：資訊處理

科    目：資料結構

考試時間：2小時                                     座號：____________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、給定一個以一維陣列 A[i] 所表示的二元樹 (binary tree) 如下：（每小題5分，共30分）

(一)請問該樹樹高為何？

(二)請列舉該樹所有葉節點 (leaf node)。

(三)A[i] 所代表的節點之左子節點 (left-child node) 應在陣列 A[.] 的那一個位置？請寫出公式。

(四)請寫出該樹之後序遍歷 (Postorder Traversal) 結果。

(五)請寫出該樹之前序遍歷 (Preorder Traversal) 結果。

(六)請寫出該樹之中序遍歷 (Inorder Traversal) 結果。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下(average case)，搜尋 (search)、插入 (insertion)、刪除 (deletion) 資料之時間複雜度。陣列的各項資料已事先填入作為範例。（每小題5分，共20分）

<圖10>pic10

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、給定如下圖所示之兩個環狀單向鏈結串列 (circular singly linked list)，並以A，B 分別指向其中兩個串列中的一個節點，另有一個指標 C 可以使用。請用類 C 之虛擬語言 (C-like pseudo code) 完成下列動作。

(一)請用至多二行虛擬碼程式刪除 C 所指向節點。結果必須維持環狀單向鏈結串列。（5分）

(二)請用至多二行虛擬碼程式將 B 所指向串列插入 A 所指向串列。結果必須維持環狀單向鏈結串列。（10分）

(三)請用至多四行虛擬碼程式寫出可將 B 所指向節點插入至 A 所指向節點之「前」，但必須維持環狀單向鏈結串列。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、給定下列數列，若以快速排序法 (Quick Sort)、選擇排序法 (Selection Sort)、堆積排序法 (Heap Sort)、泡沫排序法 (Bubble Sort) 進行排序。請問下列數列是那一個排序法排序過程的暫時結果，並說明之。（每小題5分，共20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852