- 1.
- 給定二元樹(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 分)
- 題型：問答題
- 難易度：尚未記錄
- 2.
- 遊樂園設計公司正在設計新的遊樂園,遊樂園將有 9 個遊樂設施,設施名稱暫定為A, B, C, D, E, F, G, H, I 。遊樂設施之間將透過不盡相同距離但極具特色的商店街相連。給定遊樂園的初步規劃如表一,表內數字為兩遊樂設施之間商店街道之預計長度(每條街道長度皆不同)。若無數字則代表兩遊樂設施之間沒有商店街道之規劃。設計公司將依不同考量來決定實際建置那些商店街道。
( 一 ) 若要節省開發預算,在可到達所有遊樂設施的前提下,所建置的商店街道總長度需越短越好,請問可以用那一個演算法來選擇應建置的街道?請給演算法名稱並簡單說明該演算法特性。( 5 分)
( 二 ) 請計算符合上述 ( 一 ) 小題條件下,所應建置的商店街道總長度,並由小到大列舉所有應該建置街道的長度。( 10 分)
( 三 ) 但若要規劃一條路徑,使得遊客可以從任一遊樂設施開始玩,且只要依照該路徑行走,就可以玩遍 9 項遊樂設施並回到起始的遊樂設施,遊客所需走過的商店街道總長度需越短越好且每項遊樂設施只能到達一次。請問此問題最適合用下列那一種演算法來幫忙找到所應開發的街道:尤拉迴路 (Euler Cycle) ,漢密爾頓迴路 (Hamiltonian Cycle) ,旅行商人問題 (Traveling Sales Man Problem) ,最短路徑(例如 Dijkstra 演算法),任兩點最短距離(例如弗洛伊德 (Floyd-Warshall)演算法)?( 5 分)
- 題型：問答題
- 難易度：尚未記錄
- 3.
- 表二列出五種常見的排序演算法,請填滿該表以顯示各排序法在最佳情況、一般情況、最壞情況下的時間複雜度、所需額外記憶體空間及是否為穩定排序法。快速排序法的各項資料已事先填入作為範例。( (a), (b), (c), (d) 各 5 分,共 20 分)
- 題型：問答題
- 難易度：尚未記錄
- 4.
- 矩陣相乘是問題解決中常見的計算,但相乘順序對於計算效能有極大的影響。給定n 個矩陣, A1 , A2 , " , An ,且任一矩陣 Ai 大小為 pi−1 × pi , p0 , " pn 皆為正整數。 A1 × A2 × … × An 實 際 計 算 過 程 可 以 是 ( … (( A 1 × A2 ) × A3 ) × … × An ) 、 ( A1 × ( A2 × ( …× ( An−2 × ( An−1 × An )) " ))) 、或其他合理的順序,而因矩陣相乘順序不同,所需要的乘法運算次數可能也會不同。透過動態規劃 (dynamic programming) 、二維陣列的應用及遞迴程式,可以找到最少乘法運算次數的計算順序。方法如下:令 m[i, j] 為計算 Ai × Ai+1 × … × Aj 時所需最少乘法運算次數, m[i, j] 可以下列遞迴公式表示之:
( 一 ) 請說明 A1 × A2 × … × An 相乘過後的矩陣大小為何?( 3 分)
( 二 ) 透過上述方法所找到的最少乘法運算次數,應為二維陣列 m[i, j] 中的那個元素,亦即 i, j 應分別為何?( 3 分)
( 三 ) 若 n = 4 且 p0 , p1 , p2 , p3 , p4 分別為 3, 4, 5, 4, 2 ,請計算並填寫出二維陣列 m[i, j] 。( 11 分)
( 四 ) 承上小題 ( 三 ) ,請說明該四矩陣相乘, A1 × A2 × A3 × A4 ,最少共需有幾次乘法運算。( 3 分)
- 題型：問答題
- 難易度：尚未記錄
- 5.
- 請依序將 17, 23, 36, 13, 38, 11, 52, 44, 25, 35, 2, 18, 21 儲存至下列 13 桶 (buckets) × 1 槽(slots) 的雜湊表 (hashing table) 。請以各小題所設定的雜湊函式 (hashing function) 將資料依序存入並顯示最後的雜湊表。
( 一 ) 雜湊函式 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 分)
- 題型：問答題
- 難易度：尚未記錄