阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
101年 - 101年三等關務特考資料結構#45156
> 申論題
題組內容
五、
⑵將收 到的 1001010101001011110010111100 字串解碼,列出文字訊息。(20 分) [註 1:建立霍夫曼樹時,比重較小的子樹成左邊子樹,比重較大的子樹成右邊子樹。 註 2:當編碼時,左邊(left edge)是 0,右邊(right edge)是 1。]
相關申論題
一、復原(undo)是文字編輯器的一個功能,可將最近的編輯操作取消,將文件恢復成 先前狀態。試設計合適的資料結構及相關運作,以達成此功能。(10 分)
#151009
二、一個多人參與的電腦遊戲,在每一回合,將錢最多的人其三分之一的錢分給錢最少 的人。試設計一個有效率的資料結構,並請說明所需儲存的資料、相關運算及時間 複雜度。(15 分)
#151010
三、當飛機航班客滿或超額預約(overbooked)時,在機場航空公司櫃台常有機位候補 (standby)的長龍。候補優先次序是由乘客的購票價格、累積里程數及要求候補的 時間先後等因素決定優先權(priority)。請設計一個有效率的資料結構及其運算 (operations)來處理候補,並說明其時間複雜度。(15 分)
#151011
⑴描述 Kruskal 演算法對一個無向權重圖(undirected weighted graph)找出最小生成 樹(minimum spanning tree)的步驟,並分析其計算複雜度。
#151012
⑵設計合適的資料結 構以儲存在過程中產生的多個連結組件(connected components),並能有效率的決 定是否採用或丟棄端點為(u,w)的一個邊(edge(u,w)),請說明。(20 分)
#151013
⑴資料壓縮可以減少資料儲存空間或網路資料傳輸量,文字資料常使用霍夫曼編碼 (Huffman coding)作壓縮。在文件中現有六個文字訊息 A, B, C, D, E, F,其出現的次 數各為 16, 12, 9, 6, 7, 2。請建立霍夫曼樹,並列出 A, B, C, D, E, F 的霍夫曼碼。
#151014
(1)2-3 樹(2-3 tree)
#151016
(2)AVL 樹(AVL tree)
#151017
(3)最大堆(Max-Heap) (4)排序陣列(sorted array increasing order),試就搜尋(search key)、刪除(delete key)、插入(insert key)、列印全部排序(print all nodes in order)及找最大值 (find Max)等運算,比較其時間複雜度。(20 分) [註:請以表格列表呈現]
#151018
(五)若 n = 10,且每一組球生產後放上裝箱輸送帶的 球的大小順序非固定順序 。假設輸送帶上原本配置 n 個機器人,若改成配置 2n 個機器人, 整組球順序排好的速度可以加快多少?請說明。
#560494
相關試卷
114年 - 114 地方政府公務特種考試_三等_資訊處理:資料結構#134706
114年 · #134706
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
114年 · #133251
114年 - 114 高等考試_三級_資訊處理:資料結構#128753
114年 · #128753
114年 - 114 關務特種考試_三等_資訊處理(選試英文):資料結構#126563
114年 · #126563
114年 - 114 身心障礙特種考試_三等_資訊處理:資料結構#126562
114年 · #126562
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理:資料結構#124511
113年 · #124511
113年 - 113 高等考試_三級_資訊處理:資料結構#121217
113年 · #121217
113年 - 113 關務特種考試_三等_資訊處理(選試英文):資料結構#119489
113年 · #119489
112年 - 112 地方政府特種考試_三等_資訊處理:資料結構#118368
112年 · #118368
112年 - 112 公務升官等考試_薦任_資訊處理:資料結構#117327
112年 · #117327