申論 1圖（graph）的表示法（Graph Representation）㈠以下面的無向圖（undirected graph）為例，說明圖的鄰接串列（adjacency list）表示法。（10 分）㈡以下面的有向圖（directed graph）為例，說明圖的鄰接矩陣（adjacency matrix）表示法。（5 分）㈢給一n 個節點（vertex）的有向圖G 的鄰接矩陣，請問計算圖G 的一個節點的出分支度（out degree）的時間複雜度為何？（5 分）㈣給一n 個節點（vertex）的有向圖G 的鄰接矩陣，請簡述判斷圖G 是否連通（connected）的演算法。（5 分）
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2霍夫曼碼（Huffman code）是一種依照字母出現的頻率決定編碼的不定長二進位編碼法（variable-length binary code）。㈠說明霍夫曼碼的編碼與解碼原理。（10 分）㈡假設字母集為 {甲、乙、丙、丁、戊、己}，個別字母出現頻率如下表。請填寫每個字母的霍夫曼碼。（15 分）字母 甲 乙 丙 丁 戊 己出現頻率 45 13 12 16 9 5霍夫曼碼年公務人員高等考試三級考試試題 代號：35450類 科： 資訊處理科 目： 資料結構
申論 3遞迴演算法（recursive algorithm）㈠令A 為N 個數的整數陣列（Integer array）。請用虛擬碼（Pseudo Code）描述求陣列A 中最大值的遞迴演算法。（5 分）㈡令A 為N 個數的整數陣列（Integer array）。假設A 中的數字已經由小到大排列好。請用儘量接近程式語言的虛擬碼（Pseudo Code）描述搜尋整數X 是否存在陣列A 中的二元搜尋（Binary Search）的遞迴演算法（recursive algorithm）。請說明此一搜尋法的時間複雜度。（10 分）㈢請用儘量接近程式語言的虛擬碼（pseudo code）描述計算費氏數列（Fibonaccinumbers）第N 項的遞迴演算法。請問該遞迴演算法的時間複雜度（timecomplexity）是否為多項式時間（polynomial time）複雜度？（10 分）
申論 4堆積排序（Heap Sort）㈠堆積排序將堆積樹（heap tree）用一個陣列（array）A 儲存。陣列的指標（index）從1 到N。請說明堆積樹的根（root）在陣列中的位置。請說明陣列（array）A 第i 個位置A[i] 所儲存的堆積樹節點的左子節點（left child）、右子節點（rightchild）、以及父節點（parent）各自在陣列A 中的位置。（5 分）㈡在Max-堆積樹中，除了根節點（root）外，每一個節點所儲存的數小於或等於其父節點所儲存的數。假設陣列A 儲存一個十個節點的Max-堆積樹。陣列A 中的數字從第一個位置到第10 個位置所存數字依序為16, 14, 10, 8, 7, 9, 3, 2, 4, 1。請畫出陣列A 所儲存的堆積樹以及各節點所儲存的數。（5 分）㈢請以儘量接近程式語言虛擬碼描述如何將一個不符合Max-堆積樹性質的陣列轉換成符合Max-堆積樹性質的陣列。請分析你的演算法的時間複雜度。（15 分）