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

復原（undo）是文字編輯器的一個功能，可將最近的編輯操作取消，將文件恢復成 先前狀態。試設計合適的資料結構及相關運作，以達成此功能。（10 分）

假設a 為一個整數陣列（array of integers），請寫一個遞迴函式（recursive function）以求出陣列中之最大元素值。（10 分） 請寫一個遞迴函式（recursive function）依序列印出完成河內塔（Towers of Hanoi） 要求所需要的移動。（10 分）

假設我們有一個由26 個英文字母所構成的文字檔。 請說明如何建構一棵霍夫曼樹（Huffman tree）來壓縮該文字檔。（15 分） 請說明如何利用你所述之方法建構的霍夫曼樹壓縮該文字檔。（5 分） 請說明如何解壓縮利用你所述方法壓縮的文字檔。（5 分）

一個多人參與的電腦遊戲，在每一回合，將錢最多的人其三分之一的錢分給錢最少 的人。試設計一個有效率的資料結構，並請說明所需儲存的資料、相關運算及時間 複雜度。（15 分）

請問下面各題所列的二種走訪結果是否定義唯一的二元樹？ （假設二元樹上的每一節點只包含單一字母的資訊而已。） 前序走訪： A B D G C E H F 中序走訪： D G B A H E C F 中序走訪： E G L M P Q R X 後序走訪： E L G Q P X R M 前序走訪： A B D F H C E G 後序走訪： H F D B G E C A 如果是唯一的話，請畫出具該二種走訪結果的二元樹。（20 分）

下列的虛擬碼程式片段中，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年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面）

當飛機航班客滿或超額預約（overbooked）時，在機場航空公司櫃台常有機位候補 （standby）的長龍。候補優先次序是由乘客的購票價格、累積里程數及要求候補的 時間先後等因素決定優先權（priority）。請設計一個有效率的資料結構及其運算 （operations）來處理候補，並說明其時間複雜度。（15 分）

假設我們有以下的鍵值（key）：7、16、49、82、5、31、6、2、44。 請畫出每個值插入堆積後的最大堆積（max heap）。（10 分） 請畫出每個值插入堆積後的最小堆積（min heap）。（10 分）

堆積（heap）是一棵完整二元樹（complete binary tree），每個節點儲存一個鍵值（key value），且每一個內部節點（internal node）的鍵值都不比其子節點的鍵值小。 請畫一棵七個節點的堆積，其節點儲存的鍵值形成的集合為 {100, 10, 55, 69, 38, 27, 48}。（5 分） 請說明如何利用陣列（array）實做一棵n 個節點的堆積。（5 分） 假設一棵n 個節點的完整二元樹，其每個節點儲存一個鍵值，除了根節點（root） 之外，其他內部節點的鍵值均不比其子節點的鍵值小。請用虛擬碼描述將這樣的 一棵二元樹調整成堆積的演算法。（10 分） 請說明如何利用上述演算法將一棵n 個節點之堆積的根節點儲存的鍵值刪除，得 到一棵儲存其餘n–1 個鍵值的堆積。（5 分）

描述Kruskal 演算法對一個無向權重圖（undirected weighted graph）找出最小生成 樹（minimum spanning tree）的步驟，並分析其計算複雜度。設計合適的資料結 構以儲存在過程中產生的多個連結組件（connected components），並能有效率的決 定是否採用或丟棄端點為(u,w)的一個邊（edge(u,w)），請說明。（20 分）

假設有一組資料35、51、54、60、71、83、85、97、107、117、127， 請分別列出使用二元搜尋（binary search）與費氏搜尋（Fibonacci search）該組資 料時的搜尋軌跡（可用二元樹表示之）。（7 分） 若尋找83 與117 二個數字，請分別求出上列兩種搜尋所需的搜尋次數。（7 分） 請說明費氏搜尋優於二元搜尋之處。（6 分） 101年公務人員特種考試警察人員考試、 101年公務人員特種考試一般警察人員考試及 101年特種考試交通事業鐵路人員考試試題 類 科： 資訊處理 全一張 （背面）

我們想設計一個動態資料結構儲存數字集合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 分）

資料壓縮可以減少資料儲存空間或網路資料傳輸量，文字資料常使用霍夫曼編碼 （Huffman coding）作壓縮。在文件中現有六個文字訊息A, B, C, D, E, F，其出現的次 數各為16, 12, 9, 6, 7, 2。請建立霍夫曼樹，並列出A, B, C, D, E, F 的霍夫曼碼。將收 到的 1001010101001011110010111100 字串解碼，列出文字訊息。（20 分） ［註1：建立霍夫曼樹時，比重較小的子樹成左邊子樹，比重較大的子樹成右邊子樹。 註2：當編碼時，左邊（left edge）是0，右邊（right edge）是1。］ 六、每筆記錄是一對（關鍵值, 資料值）（key, data values），當N 筆資料以下列資料結 構儲存時：(1)2-3 樹（2-3 tree） (2)AVL 樹（AVL tree） (3)最大堆（Max-Heap） (4)排序陣列（sorted array increasing order），試就搜尋（search key）、刪除（delete key）、插入（insert key）、列印全部排序（print all nodes in order）及找最大值 （find Max）等運算，比較其時間複雜度。（20 分） ［註：請以表格列表呈現］

針對下圖之邊活動（Activity-on-Edge；AOE）網路，計算它每個活動的最早與最 晚開始時間。利用前向－後向方法（forward-backward approach）。（4 分） 這個計畫的最早完成時間為何？（4 分） 那些活動是臨界（critical）活動？（4 分） 請畫出其臨界網路。（4 分） 是否存在一個活動，當我們加速它的工作時間時會造成整個計畫時程縮短？（4 分） 0 1 3 5 2 4 7

8 9 start finish a3=3 a5=3 a7=4 a10=4 a12=5 a14=2 a6=3 a11=2 a13=4 a8=4 a1=5 a2=6 a9=1 a4=6