阿摩線上測驗 登入

96年 - 096年高等三級暨普通資料結構#55861

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

試卷資訊

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

選擇題 (0)

申論題 (12)

【已刪除】⑴以下面的無向圖（undirected graph）為例，說明圖的鄰接串列（adjacency list）表 示法。（10 分）
【已刪除】⑵以下面的有向圖（directed graph）為例，說明圖的鄰接矩陣（adjacency matrix） 表示法。（5 分）
⑶給一 n 個節點（vertex）的有向圖 G 的鄰接矩陣，請問計算圖 G 的一個節點的出 分支度（out degree）的時間複雜度為何？（5 分）
⑷給一 n 個節點（vertex）的有向圖 G 的鄰接矩陣，請簡述判斷圖 G 是否連通 （connected）的演算法。（5 分）
⑴說明霍夫曼碼的編碼與解碼原理。（10 分）
⑵假設字母集為 {甲、乙、丙、丁、戊、己}，個別字母出現頻率如下表。請填寫 每個字母的霍夫曼碼。（15 分）
⑴令 A 為 N 個數的整數陣列（Integer array）。請用虛擬碼（Pseudo Code）描述求 陣列 A 中最大值的遞迴演算法。（5 分）
⑵令 A 為 N 個數的整數陣列（Integer array）。假設 A 中的數字已經由小到大排列 好。請用儘量接近程式語言的虛擬碼（Pseudo Code）描述搜尋整數 X 是否存在 陣列 A 中的二元搜尋（Binary Search）的遞迴演算法（recursive algorithm）。請 說明此一搜尋法的時間複雜度。（10 分）
⑶請用儘量接近程式語言的虛擬碼（pseudo code）描述計算費氏數列（Fibonacci numbers）第 N 項的遞迴演算法。請問該遞迴演算法的時間複雜度（time complexity）是否為多項式時間（polynomial time）複雜度？（10 分）
⑴堆積排序將堆積樹（heap tree）用一個陣列（array）A 儲存。陣列的指標（index） 從1 到N。請說明堆積樹的根（root）在陣列中的位置。請說明陣列（array）A 第 i 個位置 A[i] 所儲存的堆積樹節點的左子節點（left child）、右子節點（right child）、以及父節點（parent）各自在陣列 A 中的位置。（5 分）
⑵在Max-堆積樹中，除了根節點（root）外，每一個節點所儲存的數小於或等於其 父節點所儲存的數。假設陣列 A 儲存一個十個節點的Max-堆積樹。陣列 A 中的 數字從第一個位置到第 10 個位置所存數字依序為 16, 14, 10, 8, 7, 9, 3, 2, 4, 1。請 畫出陣列 A 所儲存的堆積樹以及各節點所儲存的數。（5 分）
⑶請以儘量接近程式語言虛擬碼描述如何將一個不符合Max-堆積樹性質的陣列轉換 成符合 Max-堆積樹性質的陣列。請分析你的演算法的時間複雜度。（15 分）