106年 - 106年關務特考三等-資料結構#61331

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

試卷資訊

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

選擇題 (0)

申論題 (11)

⑴請繪出完成輸入後的二元搜尋樹。（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 分）

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

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

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

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

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