阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
96年 - 096年高等三級暨普通資料結構#55861
> 申論題
題組內容
二、霍夫曼碼(Huffman code)是一種依照字母出現的頻率決定編碼的不定長二進位編 碼法(variable-length binary code)。
⑴說明霍夫曼碼的編碼與解碼原理。(10 分)
相關申論題
⑶給一 n 個節點(vertex)的有向圖 G 的鄰接矩陣,請問計算圖 G 的一個節點的出 分支度(out degree)的時間複雜度為何?(5 分)
#211258
⑷給一 n 個節點(vertex)的有向圖 G 的鄰接矩陣,請簡述判斷圖 G 是否連通 (connected)的演算法。(5 分)
#211259
⑵假設字母集為 {甲、乙、丙、丁、戊、己},個別字母出現頻率如下表。請填寫 每個字母的霍夫曼碼。(15 分)
#211261
⑴令 A 為 N 個數的整數陣列(Integer array)。請用虛擬碼(Pseudo Code)描述求 陣列 A 中最大值的遞迴演算法。(5 分)
#211262
⑵令 A 為 N 個數的整數陣列(Integer array)。假設 A 中的數字已經由小到大排列 好。請用儘量接近程式語言的虛擬碼(Pseudo Code)描述搜尋整數 X 是否存在 陣列 A 中的二元搜尋(Binary Search)的遞迴演算法(recursive algorithm)。請 說明此一搜尋法的時間複雜度。(10 分)
#211263
⑶請用儘量接近程式語言的虛擬碼(pseudo code)描述計算費氏數列(Fibonacci numbers)第 N 項的遞迴演算法。請問該遞迴演算法的時間複雜度(time complexity)是否為多項式時間(polynomial time)複雜度?(10 分)
#211264
⑴堆積排序將堆積樹(heap tree)用一個陣列(array)A 儲存。陣列的指標(index) 從1 到N。請說明堆積樹的根(root)在陣列中的位置。請說明陣列(array)A 第 i 個位置 A[i] 所儲存的堆積樹節點的左子節點(left child)、右子節點(right child)、以及父節點(parent)各自在陣列 A 中的位置。(5 分)
#211265
⑵在Max-堆積樹中,除了根節點(root)外,每一個節點所儲存的數小於或等於其 父節點所儲存的數。假設陣列 A 儲存一個十個節點的Max-堆積樹。陣列 A 中的 數字從第一個位置到第 10 個位置所存數字依序為 16, 14, 10, 8, 7, 9, 3, 2, 4, 1。請 畫出陣列 A 所儲存的堆積樹以及各節點所儲存的數。(5 分)
#211266
⑶請以儘量接近程式語言虛擬碼描述如何將一個不符合Max-堆積樹性質的陣列轉換 成符合 Max-堆積樹性質的陣列。請分析你的演算法的時間複雜度。(15 分)
#211267
(五)若 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