申論 1給定二元樹（binary tree）如右圖，樹高為4 且共有7 個節點。 TT㈠請寫出該樹之後序遍歷（postorder traversal）結果。（5 分）SSUU㈡若以陣列A[1..15]實作該二元樹，請列舉陣列A[1..15]的內容。OOGG（5 分）㈢若要將數值x 設為或取代A[i]（任一1 ≤i ≤7）所代表的節點PPXX之右子節點（right child node）的內容，令x 會被放入陣列中A[j]的位置。請以j、i 表示，寫出j 位置之公式。（5 分）㈣若要在原始的二元樹中加入一些節點使其成為完整二元樹（complete binary tree）及完滿二元樹（full binary tree），請問最少各需加入幾個新節點？（5 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2遊樂園設計公司正在設計新的遊樂園，遊樂園將有9 個遊樂設施，設施名稱暫定為A, B, C,D, E, F, G, H, I。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園的初步規劃如表一，表內數字為兩遊樂設施之間商店街道之預計長度（每條街道長度皆不同）。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決定實際建置那些商店街道。表一ABCDEFG H IA 18 5 131B18 9 1016 8C 9 11 7 12 3D5 17 19E13101117 2F1 16 14 15G 7 192 4H 12 144 6I 8 3 15 6㈠若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分）㈡請計算符合上述㈠小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分）㈢但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走，就可以玩遍9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle），旅行商人問題（Traveling Sales Man Problem），最短路徑（例如Dijkstra 演算法），任兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）106年公務人員高等考試三級考試試題 代號：26050類科：資訊處理科目：資料結構
申論 3表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資料已事先填入作為範例。（(a),(b),(c),(d)各5 分，共20 分）表二是或不是最佳情況 一般情況最壞情況所需額外空間穩定排序法（best case）（average case）（worst case）（stable sort）快速排序法 2O(n log n) O(n log n) O(n) O(n) 不是（quicksort）(a)泡沫排序法bubble sort(b)插入排序法insertion sort(c)合併排序法merge sort(d)堆積排序法heap sort
申論 4矩陣相乘是問題解決中常見的計算，但相乘順序對於計算效能有極大的影響。給定n 個矩陣，A, A, …, A，且任一矩陣A 大小為p ×p,p,...,p皆為正整數。A × A × … × A 實12nii−1i0n12n際計算過程可以是(…((A × A) × A) × … × A)、(A × (A × (…× (A × (A × A))…)))、或123n12n-2n-1n其他合理的順序，而因矩陣相乘順序不同，所需要的乘法運算次數可能也會不同。透過動態規劃（dynamic programming）、二維陣列的應用及遞迴程式，可以找到最少乘法運算次數的計算順序。方法如下：令m[i,j]為計算A × A × … × A 時所需最少乘法運算次數，ii+1jm[i,j]可以下列遞迴公式表示之：⎧min{m[i,k]+m[k+,1j]+ppp},ifi<jm[i,j]=⎨i−1kji≤k<j⎩,0ifi≥j㈠請說明A × A × … × A 相乘過後的矩陣大小為何？（3 分）12n㈡透過上述方法所找到的最少乘法運算次數，應為二維陣列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 分）
申論 5請依序將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 6 7 8 9 101112湊表㈠雜湊函式F(x) = x mod 13，碰撞時，採取「線性探測法」（open addressing with linearprobing）來放入資料。請顯示最後的雜湊表。（5 分）㈡雜湊函式F(x) = x mod 13，碰撞時，採取「二次方探測法」（open addressing with quadraticprobing）來放入資料。請顯示最後的雜湊表。（5 分）㈢雜湊函式F(x) = x mod 13，碰撞時，採取「雙探測法」（open addressing with double hashing）來放入資料，第二雜湊函式為F(x) = 7－(x mod 7)。請顯示最後的雜湊表。（5 分）㈣若雜湊表夠大（例如slots = 2 或更大）但資料量多時，針對三種碰撞時所採取的處理方式，請說明那一種方式較能有效率的儲存或搜尋資料？請說明那一種處理方式效率最差？（5 分）