加載中. ..
PDF
106年公務人員特種考試關務人員考試、
106年公務人員特種考試身心障礙人員考試及
106年國軍上校以上軍官轉任公務人員考試試題 代號：10460 全一頁
考試別： 關務人員考試
等別： 三等考試
類科： 資訊處理
科目： 資料結構
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
（請接背面）
一、一個二元搜尋樹（binary search tree）初始為空的，依序插入（insert）5,11,9,24,10,2,15,3。
請繪出完成輸入後的二元搜尋樹。（10 分）
試說明如何利用一維陣列來表示（represent）此二元搜尋樹，並在此一維陣列中保
有此樹狀結構父節點與子節點的關係性。（5分）
請設計一演算法能將此二元搜尋樹，依數值由大到小的方式輸出。（5分）
對產生的二元搜尋樹，刪除數值 5。請繪出完成刪除動作後的二元搜尋樹。
（5分）
二、請使用 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分）
三、一個工廠有 n台機器 M1,M2, …,Mn 及k份工作 J1, J2, …, Jk，每份工作都有其所需的
執行時間 T（J1）, T（J2）, …,T（Jk）。每一台機器一次只能執行一份工作，每份工
作只能交給一台機器執行，n台機器可同時執行 n份不同的工作。
請設計一個 Greedy（貪婪）的演算法，來解決工作排程的問題，使得完成 k份工
作的時間最短。（15 分）
此Greedy 演算法適合使用何種資料結構來完成？（5分）
此Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5分）
四、有一雜湊表格（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 分）