阿摩線上測驗 登入

102年 - 102年地方三等考試-三等資料結構#43740

科目：公職◆資料結構 | 年份：102年 | 選擇題數：0 | 申論題數：10

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (10)

⑴由 a 點出發，做 depth-first traversal（深度優先拜訪），請問那些節點（node）不 會被訪問到？（3 分）
⑵由 a 點出發，做 breadth-first traversal（寬度優先拜訪），請問那些節點（node） 不會被訪問到？（2 分）
【已刪除】 ⑶假設圖 1 代表 heap 上各個節點（node）及其相互指向的關係。p、q、r 三節點代 表全域變數（global variables），其他的節點代表 heap 上的記憶體區塊。如果 p→a 的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾 節點的方法及所需之資料結構。你的演算法只能從 a 節點出發，它必須指出所有 的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演 算法必須在每一個節點儲存那些資料？（15 分）     
⑴請問 F(11) =？（5 分）
⑵請證明對於任何正整數 w，我們都可以在有限時間內計算 F(w)。（提示：每個奇 數可以寫成(2i + 1)2k – 1 的形式，再採用數學歸納法來證明。）（15 分）
【已刪除】三、Knuth，Morris 及 Pratt 發明了一個快速的字串比對方法（string pattern matching）。 他們的方法採用一個失敗函數（failure function）。失敗函數其實就是一個輔助的資 料結構，用來加速比對。請依他們的方法計算下列字串的失敗函數。你必須說明失 敗函數的定義為何，以及失敗函數如何加速比對。（15 分） 
【已刪除】四、請參考圖 2。每一條線段上的數字代表兩節點間的距離。請找出 a 節點到 k 節點的 最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15 分） 
【已刪除】五、請參考圖 3。圖 3 是一個 activity-on-edge 網路。在 activity-on-edge 網路中，一項計 畫可以分成很多件工作，每一件工作由一條線段代表，線段上的數字代表該工作所 需的時間（以工作日為單位），線段的箭頭代表工作的先後關係。例如在圖 3 中， ab 及 db 線段代表的工作完成之後，bc、be、及 bf 線段代表的工作才可以開始進行， 其他的先後關係依此類推。a 節點是起點，k 節點是全部工作的完成點。請找出 k 節點的最早完成時間及關鍵路線（critical path）。並請說明你的方法如何應用在非 常大型的圖裡。（15 分） 
⑴如果一個二元樹有 n 個節點，那麼它有幾個空指標？（5 分）
【已刪除】 ⑵我們可以利用原本是空指標的欄位來儲存引線（threads）。二元樹加上引線的結 果稱為引線樹（threaded trees）。當然我們必須在各節點再加上兩個欄位 LTAG 及 RTAG，共 5 個欄位，如下圖所示：如果 LEFT 欄位代表一般的節點指標，則 LTAG = 0。如果 LEFT 欄位代表引線指標， 則 LTAG = 1。同理，如果 RIGHT 欄位代表一般的節點指標，則 RTAG = 0。如果 RIGHT 欄位代表引線指標，則 RTAG = 1。 請將下圖的二元樹加上適當的引線指標，讓它變成引線樹，並請繪圖標出 A 到 I 共 9 個節點中所有引線指標指向的節點。（10 分）