申論 1假設我們有一個由26 個英文字母所構成的文字檔。㈠請說明如何建構一棵霍夫曼樹（Huffman tree）來壓縮該文字檔。（15 分）㈡請說明如何利用你所述之方法建構的霍夫曼樹壓縮該文字檔。（5 分）㈢請說明如何解壓縮利用你所述方法壓縮的文字檔。（5 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2下列的虛擬碼程式片段中，I 和S 均為遞迴函式（recursive function），I 和S 的參數A 是一個整數陣列；I 和S 的參數i 為不為負的整數，主要是做為陣列A 的索引（index）。假設陣列A 的元素個數為n，且其索引值為0 到n–1 之間的數值。虛擬碼swap x and y 的意思是將變數x 與變數y 的儲存值互換；亦即執行之後變數x的儲存值為執行前變數y 的儲存值，執行之後變數y 的儲存值為執行前變數x 的儲存值。令T(n)為呼叫函式I(A, n–1)的執行時間。T(n)會隨著陣列A 所儲存的數值不同而有所不同。S(A, i) {If i <= 0, then return;S(A, i – 1);I(A, i);Return; }I(A, i) {If i <= 0, then return;If A[i] < A[i – 1] {swap A[i] and A[i – 1] ;I(A, i – 1); }Return; }㈠請用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 分）101年公務人員高等考試三級考試試題 代號：36250類 科： 資訊處理科 目： 資料結構
申論 3堆積（heap）是一棵完整二元樹（complete binary tree），每個節點儲存一個鍵值（keyvalue），且每一個內部節點（internal node）的鍵值都不比其子節點的鍵值小。㈠請畫一棵七個節點的堆積，其節點儲存的鍵值形成的集合為{100, 10, 55, 69, 38, 27, 48}。（5 分）㈡請說明如何利用陣列（array）實做一棵n 個節點的堆積。（5 分）㈢假設一棵n 個節點的完整二元樹，其每個節點儲存一個鍵值，除了根節點（root）之外，其他內部節點的鍵值均不比其子節點的鍵值小。請用虛擬碼描述將這樣的一棵二元樹調整成堆積的演算法。（10 分）㈣請說明如何利用上述演算法將一棵n 個節點之堆積的根節點儲存的鍵值刪除，得到一棵儲存其餘n–1 個鍵值的堆積。（5 分）
申論 4我們想設計一個動態資料結構儲存數字集合S={0, 1, 2, …, n – 1}的倆倆沒有交集，而且聯集等於S 的子集合。初始時有n 個元素，個數為1 的子集合，分別為{0}, {1}, …, {n – 1}。我們希望這個資料結構可以支援以下兩個功能：union(x, y): x, y ∈ S。union(x, y)將包含x 的子集合與包含y 的子集合聯集得到一個新的子集合，原來的子集合不再存在。equivalence(x, y): x, y ∈ S。equivalence(x, y)判斷x 與y 是否屬於同一個子集合，若屬於同一個子集合，則回傳“TRUE”，否則回傳“FALSE”。上述兩個函式必須能夠依任何順序交替執行。㈠請描述一個可以達成上述需求而且union(x, y)與equivalence(x, y)的時間複雜度均為O(log n)的資料結構。（15 分）㈡請用虛擬碼描述可以在上述資料結構運作的union(x, y)函式。（5 分）㈢請用虛擬碼描述可以在上述資料結構運作的equivalence(x, y)函式。（5 分）