阿摩線上測驗 登入

98年 - 098年3等資料結構#48188

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

試卷資訊

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

選擇題 (0)

申論題 (9)

一、有 N 份資料，每份資料皆以兩個大寫英文字母標記（例如 AK、TA 等等）。請設計 一 O(N) 時間的演算法，將此組資料依標記的字典順序排序，並請說明此演算法所 需使用的空間。（20 分）
⑴請分別用鄰接矩陣（adjacency matrix）與鄰接串列（adjacency list）的方式表示圖 形 G。（10 分）
⑵請在標記小的節點先搜尋的規則下，產生以節點 0 為起始節點的廣度優先搜尋擴 張 樹 （ breadth-first search spanning tree ） 與 深 度 優 先 搜 尋 擴 張 樹 （ depth-first search spanning tree）。（10 分）
⑴請寫一使用 O(log N)次乘法運算的遞迴（recursive）程式計算 a 的 N 次方。（10 分）
⑵請寫一使用 O(log N)次乘法運算的疊代（iterative）程式計算 a 的 N 次方。（10 分）
⑴設h2(k) ≣ 1，請列出最後雜湊表的結果與使用雜湊函數的次數。（10 分）
⑵設h2(k) = 1 + k (mod 13)，請列出最後雜湊表的結果與使用雜湊函數的次數。 （10 分）
⑴若以下列不定長度二進位編碼（variable-length binary code）來編碼此檔案，請問 每個字母平均用幾個位元表示？（5 分） 
⑵霍夫曼碼（Huffman code）是一種與檔案中字母出現頻率有關的不定長度二進位 編碼法，檔案經其編碼後，長度是所有不定長度二進位編碼中最短的。請為此檔 案建立其霍夫曼碼，並算出此編碼下每個字母平均用幾個位元表示。（15 分）