106年 - 公務人員升官等薦任/資料結構#66350

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

試卷資訊

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

選擇題 (0)

申論題 (15)

⑴請列出對應同一圖 G 之相鄰串列（adjacency list）。（5 分）

⑵其最小生成樹（minimum spanning tree）為何？（5 分）

⑶請問此圖是否為連通圖（connected graph）？為什麼？（5 分）

⑷請問此圖是否為雙連通圖（biconnected graph）？為什麼？（5 分）

⑴請將此字串（包含空白字元）用 Huffman coding 演算法編碼，並將編碼過程及結果寫出。（10 分）

⑵若以字串集{ she, sells, seashells, by, the, seashore }建立一字典樹（trie），請問結果為何？（10 分）

⑴若插入另一數字 10，請問此最大堆積內部資料依序為何？（5 分）

⑵請利用⑴所得之最大堆積，以堆積排序法（heap sort）將其由小到大排序，並列出每回合最大堆積的結果。（10 分）

⑶設計堆積排序法時，最適合的資料結構為何？為什麼？（5 分）

⑴若此數列存於一維陣列中，以二元搜尋法尋找資料，經幾次比較運算可找到 5？一般來說，最差情形幾次比較運算可找到？（5 分）

⑵若以此數列順序，建立二元樹，所得之二元樹為何？（5 分）

⑶若以此數列順序，建立三階 B 樹（B tree of order 3），所得之 B 樹為何？（10 分）

⑴其相應之相鄰矩陣（adjacency matrix）為何？（5 分）

⑵從 A 點開始，進行深度優先搜尋（depth-first search），所經之節點順序為何？請以字母較小節點優先輸出。（5 分）

⑶若 dfs(i)是以節點 i 出發進行深度優先搜尋的副程式，請利用 dfs(i)寫出可判斷圖形是否連通（connected）的演算法，並分析其時間複雜度。（10 分）