加載中. ..
PDF
106年公務、關務人員升官等考試、106年交通
事業鐵路、公路、港務人員升資考試試題
代號：26260
全一頁
等
級
：
薦任
類科
（
別
）
：
資訊處理
科目
：
資料結構
考試時間
： 2
小時
座號
：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
（請接背面）
一、下列二維陣列為某圖 G之相鄰矩陣（adjacency matrix）：
A B C D E F G H
A 0 1 0 1 2 0 0 0
B 1 0 1 0 0 2 0 0
C 0 1 0 1 0 0 2 0
D 1 0 1 0 0 0 0 2
E 2 0 0 0 0 3 0 3
F 0 2 0 0 3 0 3 0
G 0 0 2 0 0 3 0 3
H 0 0 0 2 3 0 3 0
請列出對應同一圖 G之相鄰串列（adjacency list）。（5分）
其最小生成樹（minimum spanning tree）為何？（5分）
請問此圖是否為連通圖（connected graph）？為什麼？（5分）
請問此圖是否為雙連通圖（biconnected graph）？為什麼？（5分）
二、給定一字串“she sells seashells by the seashore”：
請將此字串（包含空白字元）用 Huffman coding 演算法編碼，並將編碼過程及結
果寫出。（10 分）
若以字串集{ she, sells, seashells, by, the, seashore }建立一字典樹（trie），請問結果
為何？（10 分）
三、若ㄧ最大堆積（max heap）內部儲存下列數列：
9, 6, 8, 4, 2, 5, 7, 3, 1
請問：
若插入另一數字 10，請問此最大堆積內部資料依序為何？（5分）
請利用所得之最大堆積，以堆積排序法（heap sort）將其由小到大排序，並列出
每回合最大堆積的結果。（10 分）
設計堆積排序法時，最適合的資料結構為何？為什麼？（5分）
四、考慮一數列 9, 8, 7, 6, 5, 4, 3, 2, 1：
若此數列存於一維陣列中，以二元搜尋法尋找資料，經幾次比較運算可找到 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 分）