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

一個二元搜尋樹（binary search tree）初始為空的，依序插入（insert）5,11,9,24,10,2,15,3。 請繪出完成輸入後的二元搜尋樹。（10 分） 試說明如何利用一維陣列來表示（represent）此二元搜尋樹，並在此一維陣列中保 有此樹狀結構父節點與子節點的關係性。（5 分） 請設計一演算法能將此二元搜尋樹，依數值由大到小的方式輸出。（5 分） 對產生的二元搜尋樹，刪除數值5。請繪出完成刪除動作後的二元搜尋樹。 （5 分）

下列二維陣列為某圖G 之相鄰矩陣（adjacency matrix）： A B C D E F G H A 0 1 0 1

串列（list or sequence）是一個函數，從整數的子集合對應到另一個集合。請寫出 兩個集合s1,s2 及一個函數f 來定義串列 [2,2,1,3]。（10 分） 分別使用Java ArrayList 及Java LinkedList 來實作上述的串列，請分別畫出草圖 （sketch）表示之（注意：兩種資料結構的草圖上，都要註明索引index）。（10 分）

給定二元樹（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 分）

請使用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 分）

0 0 0 B 1 0 1 0 0 2 0 0 C 0 1 0 1 0 0 2 0 D 1 0 1 0 0 0 0 2 E 2 0 0 0 0

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

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

一個工廠有n 台機器M1,M2, …,Mn 及k 份工作J1, J2, …, Jk，每份工作都有其所需的 執行時間T（J1）, T（J2）, …,T（Jk）。每一台機器一次只能執行一份工作，每份工 作只能交給一台機器執行，n 台機器可同時執行n 份不同的工作。 請設計一個Greedy（貪婪）的演算法，來解決工作排程的問題，使得完成k 份工 作的時間最短。（15 分） 此Greedy 演算法適合使用何種資料結構來完成？（5 分） 此Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5 分）

0 3 F 0 2 0 0 3 0 3 0 G 0 0 2 0 0 3 0 3 H 0 0 0 2 3 0 3 0 請列出對應同一圖G 之相鄰串列（adjacency list）。（5 分） 其最小生成樹（minimum spanning tree）為何？（5 分） 請問此圖是否為連通圖（connected graph）？為什麼？（5 分） 請問此圖是否為雙連通圖（biconnected graph）？為什麼？（5 分） 二、給定一字串“she sells seashells by the seashore”： 請將此字串（包含空白字元）用Huffman coding 演算法編碼，並將編碼過程及結 果寫出。（10 分） 若以字串集{ she, sells, seashells, by, the, seashore }建立一字典樹（trie），請問結果 為何？（10 分） 三、若ㄧ最大堆積（max heap）內部儲存下列數列： 9, 6, 8, 4, 2, 5, 7, 3, 1 請問： 若插入另一數字10，請問此最大堆積內部資料依序為何？（5 分） 請利用所得之最大堆積，以堆積排序法（heap sort）將其由小到大排序，並列出 每回合最大堆積的結果。（10 分） 設計堆積排序法時，最適合的資料結構為何？為什麼？（5 分）

請寫出下面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); } 106年公務人員特種考試警察人員、一般警察 人員考試及106年特種考試交通事業鐵路 人員、退除役軍人轉任公務人員考試試題 全一張 （背面） 考試別： 鐵路人員考試 等 別： 高員三級考試 類科別： 資訊處理 科 目： 資料結構

D 5 17 19 E 13 10 11 17 2 F 1 16 14 15 G 7 19 2

有一雜湊表格（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 分）

考慮一數列9, 8, 7, 6, 5, 4, 3, 2, 1： 若此數列存於一維陣列中，以二元搜尋法尋找資料，經幾次比較運算可找到5？一 般來說，最差情形幾次比較運算可找到？（5 分） 若以此數列順序，建立二元樹，所得之二元樹為何？（5 分） 若以此數列順序，建立三階B 樹（B tree of order 3），所得之B 樹為何？（10 分）

將下列資料 60, 30, 80, 20, 50, 70, 90, 40, 35 依序分別加入原本為空的紅黑樹（red-black tree）及2-3-4 樹，請分別寫出結果。（20 分） 注意：紅黑樹的紅色（Red）節點，請註明R，例如：資料30 的節點是紅色的，則 請寫30R。 注意：2-3-4 樹的節點要分裂（split）時，最小資料放在左子節點，最大兩個資料放 在右子節點，次小資料放在父節點。

H 12 14 4 6 I 8 3 15 6 若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短 越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演 算法特性。（5 分） 請計算符合上述小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該 建置街道的長度。（10 分） 但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走， 就可以玩遍9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越 短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找 到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle）， 旅行商人問題（Traveling Sales Man Problem），最短路徑（例如Dijkstra 演算法），任 兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分） T S O P X G U 106年公務人員高等考試三級考試試題 全一張 （背面） 類 科：資訊處理 科 目：資料結構 三、表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最 壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資 料已事先填入作為範例。（(a),(b),(c),(d)各5 分，共20 分） 表二 最佳情況 （best case） 一般情況 （average case） 最壞情況 （worst case） 所需額外空間 是或不是 穩定排序法 （stable sort） 快速排序法 （quicksort） O(n log n) O(n log n) O(n2) O(n) 不是 (a)泡沫排序法 bubble sort (b)插入排序法 insertion sort (c)合併排序法 merge sort (d)堆積排序法 heap sort 四、矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定n 個矩陣， A1, A2, …, An，且任一矩陣Ai 大小為 n i i p p p p ..., , , 0 1 × − 皆為正整數。A1 × A2 × … × An 實 際計算過程可以是(…((A1 × A2) × A3) × … × An)、(A1 × (A2 × (…× (An-2 × (An-1 × An))…)))、或 其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動 態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次 數的計算順序。方法如下：令 ] , [ j i m 為計算Ai × Ai+1 × … × Aj 時所需最少乘法運算次數， ] , [ j i m 可以下列遞迴公式表示之： ⎩ ⎨ ⎧ ≥ < + + + = − < ≤ j i if j i if p p p j k m k i m j i m j k i j k i ,0 }, ] ,1 [ ] , [ { min ] , [ 1 請說明A1 × A2 × … × An 相乘過後的矩陣大小為何？（3 分） 透過上述方法所找到的最少乘法運算次數，應為二維陣列 ] , [ j i m 中的那個元素，亦即i, j 應分別為何？（3 分） 若n = 4 且 4 3 2 1 0 , , , , p p p p p 分別為3, 4, 5, 4, 2，請計算並填寫出二維陣列 ] , [ j i m 。（11 分） 承上小題，請說明該四矩陣相乘，A1 × A2 × A3 × A4，最少共需有幾次乘法運算。（3 分）

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

將下列資料 60, 30, 80, 20, 50, 70, 90, 40, 35 依序分別加入原本為空的最小堆積（min heap）及空的陣列（array）中，請分別寫 出結果，表示資料儲存的情形。（10 分） 承題，分別自最小堆積及陣列中刪去30，刪除資料後，需重新建立最小堆積。 而陣列中所有在此資料右方之資料必須向左移，不可留空白，請分別寫出結果。 （10 分）

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

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

9 10 11 12 雜湊函式F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linear probing）來放入資料。請顯示最後的雜湊表。（5 分） 雜湊函式F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadratic probing）來放入資料。請顯示最後的雜湊表。（5 分） 雜湊函式F1(x) = x mod 13，碰撞時，採取「雙探測法」 （open addressing with double hashing） 來放入資料，第二雜湊函式為F2(x) = 7－(x mod 7)。請顯示最後的雜湊表。（5 分） 若雜湊表夠大（例如slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方 式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最 差？（5 分）