所屬科目：公職◆資料結構
⑴請寫出該樹之後序遍歷（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 分）
⑴若要節省開發預算，在可到達所有遊樂設施的前提下，所建置的商店街道總長度需越短越好，請問可以用那一個演算法來選擇應建置的街道？請給演算法名稱並簡單說明該演算法特性。（5 分）
⑵請計算符合上述⑴小題條件下，所應建置的商店街道總長度，並由小到大列舉所有應該建置街道的長度。（10 分）
⑶但若要規劃一條路徑，使得遊客可以從任一遊樂設施開始玩，且只要依照該路徑行走， 就可以玩遍 9 項遊樂設施並回到起始的遊樂設施，遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道：尤拉迴路（Euler Cycle），漢密爾頓迴路（Hamiltonian Cycle）， 旅行商人問題（Traveling Sales Man Problem），最短路徑（例如 Dijkstra 演算法），任 兩點最短距離（例如弗洛伊德(Floyd-Warshall)演算法）？（5 分）
三、表二列出五種常見的排序演算法，請填滿該表以顯示各排序法在最佳情況、一般情況、最 壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資料已事先填入作為範例。（(a),(b),(c),(d)各 5 分，共 20 分）
⑴請說明 A1 × A2 × … × An相乘過後的矩陣大小為何？（3 分）
⑵透過上述方法所找到的最少乘法運算次數，應為二維陣列m[i, j]中的那個元素，亦即 i, j 應分別為何？（3 分）
⑶若 n = 4 且 0 1 2 3 4 p , p , p , p , p 分別為 3, 4, 5, 4, 2，請計算並填寫出二維陣列m[i, j]。（11 分）
⑷承上小題⑶，請說明該四矩陣相乘，A1 × A2 × A3 × A4，最少共需有幾次乘法運算。（3 分）
⑴雜湊函式 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 分）
阿摩線上測驗
登入
阿摩線上測驗
登入
