阿摩線上測驗 登入

101年 - 101年高考三級資料結構#44918

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

試卷資訊

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

選擇題 (0)

申論題 (14)

⑴請說明如何建構一棵霍夫曼樹（Huffman tree）來壓縮該文字檔。（15 分）
⑵請說明如何利用你所述之方法建構的霍夫曼樹壓縮該文字檔。（5 分）
⑶請說明如何解壓縮利用你所述方法壓縮的文字檔。（5 分）
⑴請用 O-notation 表示 T( n)的上界（upper bound）；請用Ω-notation 表示 T( n)的下 界（lower bound）。（5 分）
⑵請說明 T(n)最大時，程式開始執行前陣列 A 所儲存的數值有何特性？理由為何？ （5 分）
⑶請問函式 S(A, n – 1)的時間複雜度為何？請說明理由。（5 分）
⑷請問執行函式 S(A, n – 1)後，陣列 A 儲存的內容有何特性？請證明你的觀察。 （10 分）
⑴請畫一棵七個節點的堆積，其節點儲存的鍵值形成的集合為 {100, 10, 55, 69, 38, 27, 48}。（5 分）
⑵請說明如何利用陣列（array）實做一棵 n 個節點的堆積。（5 分）
⑶假設一棵 n 個節點的完整二元樹，其每個節點儲存一個鍵值，除了根節點（root） 之外，其他內部節點的鍵值均不比其子節點的鍵值小。請用虛擬碼描述將這樣的 一棵二元樹調整成堆積的演算法。（10 分）
⑷請說明如何利用上述演算法將一棵 n 個節點之堆積的根節點儲存的鍵值刪除，得 到一棵儲存其餘 n – 1 個鍵值的堆積。（5 分）
⑴請描述一個可以達成上述需求而且 union (x, y)與 equivalence (x, y)的時間複雜度均 為 O (log n)的資料結構。（15 分）
⑵請用虛擬碼描述可以在上述資料結構運作的 union(x, y)函式。（5 分）
⑶請用虛擬碼描述可以在上述資料結構運作的 equivalence( x, y)函式。（5 分）