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

已知一棵二元樹（binary tree）的前序走訪（preorder traversal）與中序走訪（inorder traversal）之結果分別如下：（每小題10 分，共20 分） 前序－A B D E G H C F I 中序－D B G E H A C I F ㈠請繪出這棵二元樹。 ㈡這棵二元樹的後序走訪（postorder traversal）結果為何？

請找出並且從小到大依序列出下列有向圖（directed graph）中，從頂點A 到所有其 他頂點的最短路徑（path）與路徑長度。（20 分）

考慮排序（sort）的問題：（每小題10 分，共30 分） ㈠如果要排序的資料很少，例如只有十幾筆資料，那麼你將採用快速排序法（quick sort）？合併排序法（merge sort）？還是氣泡排序法（bubble sort）？為什麼？ ㈡如果要排序的資料很多，例如多到超過主記憶體容量許多，那麼你將採用快速排 序法？合併排序法？還是氣泡排序法？為什麼？ ㈢快速排序法、合併排序法以及氣泡排序法這三個排序法當中，那一（些）排序法 是穩定的（stable）？或者都不穩定？

給予如下之Weighted Graph G：（每小題10 分，共20 分） ㈠利用 Kruskal’s algorithm 來找最小擴張樹（Minimal spanning tree）。 ㈡在演算法中有一動作：選擇一最低成本的邊（edge），加入此邊（edge），如不 形成一迴圈（cycle），則加入此邊至最小擴張樹，請問運用何運算（operations） 或原理可完成此動作？

13 15 16 12

9 pattern a b b a b c a b b a failure ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ 四、請參考圖2。每一條線段上的數字代表兩節點間的距離。請找出a 節點到k 節點的 最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15 分） 五、請參考圖3。圖3 是一個activity-on-edge 網路。在activity-on-edge 網路中，一項計 畫可以分成很多件工作，每一件工作由一條線段代表，線段上的數字代表該工作所 需的時間（以工作日為單位），線段的箭頭代表工作的先後關係。例如在圖3 中， ab 及db 線段代表的工作完成之後，bc、be、及bf 線段代表的工作才可以開始進行， 其他的先後關係依此類推。a 節點是起點，k 節點是全部工作的完成點。請找出k 節點的最早完成時間及關鍵路線（critical path）。並請說明你的方法如何應用在非 常大型的圖裡。（15 分） （請接第三頁） 圖3 Activity-on-edge 網路 圖2 最短路徑 a 22 21 11 11 21 12 12 21 13 13 19 27 23 23 5 14 b c d e f g h k a b c d e f g h k 16 11 12 13 17 23 27 21 41 10 26 49 4 5 3 7 35 14 3 7 102年特種考試地方政府公務人員考試試題 類 科： 資訊處理 全三頁 第三頁 六、在一個二元樹裡有許多節點（nodes）。假設每一個節點的資料結構如下圖： 其中DATA 欄位為該節點的資料。LEFT 欄位為指向左方子樹的指標變數。RIGHT 欄位為指向右方子樹的指標變數。 如果節點p 沒有左方子樹，其LEFT 欄位為空指標（null pointer）。同理，如果節 點p 沒有右方子樹，其RIGHT 欄位為空指標（null pointer）。 ㈠如果一個二元樹有n 個節點，那麼它有幾個空指標？（5 分） ㈡我們可以利用原本是空指標的欄位來儲存引線（threads）。二元樹加上引線的結 果稱為引線樹（threaded trees）。當然我們必須在各節點再加上兩個欄位LTAG 及RTAG，共5 個欄位，如下圖所示： 如果LEFT 欄位代表一般的節點指標，則LTAG = 0。如果LEFT 欄位代表引線指標， 則LTAG = 1。同理，如果RIGHT 欄位代表一般的節點指標，則RTAG = 0。如果 RIGHT 欄位代表引線指標，則RTAG = 1。 請將下圖的二元樹加上適當的引線指標，讓它變成引線樹，並請繪圖標出A 到I 共 9 個節點中所有引線指標指向的節點。（10 分） LEFT DATA RIGHT LTAG LEFT DATA RIGHT RTAG A B C D E F G H I