阿摩線上測驗 登入

101年 - 101年三等關務特考資料結構#45156

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

試卷資訊

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

選擇題 (0)

申論題 (10)

一、復原（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。］
(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 分） ［註：請以表格列表呈現］