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

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

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

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

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

㈠資料壓縮可以減少資料儲存空間或網路資料傳輸量，文字資料常使用霍夫曼編碼 （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 分） ［註：請以表格列表呈現］

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