資訊處理 106 年資料結構考古題

一個二元搜尋樹（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 分）

考慮下列的雙向圖： ㈠其相應之相鄰矩陣（adjacency matrix）為何？（5 分） ㈡從A 點開始，進行深度優先搜尋（depth-first search），所經之節點順序為何？請以 字母較小節點優先輸出。（5 分） ㈢若dfs(i)是以節點i 出發進行深度優先搜尋的副程式，請利用dfs(i)寫出可判斷圖形 是否連通（connected）的演算法，並分析其時間複雜度。（10 分）

9 10 11 12 13 14 15 A[i] T S U B O G P X ㈠請問該樹樹高為何？ ㈡請列舉該樹所有葉節點（leaf node）。 A[i] ㈢ 所代表的節點之左子節點（left-child node）應在陣列A[.]的那一個位置？請寫 出公式。 ㈣請寫出該樹之後序遍歷（Postorder Traversal）結果。 ㈤請寫出該樹之前序遍歷（Preorder Traversal）結果。 ㈥請寫出該樹之中序遍歷（Inorder Traversal）結果。 二、下表列出四種常見的資料結構，請填滿該表以顯示各資料結構在一般狀況下（average case），搜尋（search）、插入（insertion）、刪除（deletion）資料之時間複雜度。陣列 的各項資料已事先填入作為範例。（每小題5 分，共20 分） 搜尋 （search） 插入 （insertion） 刪除 （deletion） 陣列 O(n) O(n) O(n) ㈠佇列（queue） ㈡雙向連結串列（doubly-linked list） ㈢二元搜尋樹（binary search tree） ㈣AVL樹（AVL tree） 106年特種考試地方政府公務人員考試試題 等 別： 三等考試 類 科： 資訊處理 科 目： 資料結構 三、給定如下圖所示之兩個環狀單向鏈結串列（circular singly linked list），並以A，B 分 別指向其中兩個串列中的一個節點，另有一個指標C 可以使用。請用類C 之虛擬語 言（C-like pseudo code）完成下列動作。 ㈠請用至多二行虛擬碼程式刪除C 所指向節點。結果必須維持環狀單向鏈結串列。（5 分） ㈡請用至多二行虛擬碼程式將B 所指向串列插入A 所指向串列。結果必須維持環狀 單向鏈結串列。（10 分） ㈢請用至多四行虛擬碼程式寫出可將B 所指向節點插入至A 所指向節點之「前」，但 必須維持環狀單向鏈結串列。（15 分） 四、給定下列數列，若以快速排序法（Quick Sort）、選擇排序法（Selection Sort）、堆積 排序法（Heap Sort）、泡沫排序法（Bubble Sort）進行排序。請問下列數列是那一個 排序法排序過程的暫時結果，並說明之。（每小題5 分，共20 分） 75 93 32 81 75 89 89 99 25 78 54 75 87 12 75 28 99 93 89 81 78 87 89 75 25 75 54 75 32 12 75 28 25 28 32 75 12 75 54 75 99 78 89 89 87 75 81 93 12 25 28 32 54 75 75 75 75 78 81 87 89 99 93 89 32 75 75 81 89 25 78 54 75 87 12 75 28 89 93 99 ㈠ ㈡ ㈢ ㈣ link link link A link . . . link link link B link . . . C