加載中. ..
PDF
107
年公務人員特種考試警察人員、一般警察人員考試及
107
年特種考試交通事業鐵路人員考試試題
代號：70670 全一頁
考試別： 鐵路人員考試
等別： 高員三級考試
類科別： 資訊處理
科目： 資料結構
考試時間 ： 2 小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
本科目除專門名詞或數理公式外，應使用本國文字作答。
（請接背面）
一、若已知一個二元樹（binary tree）的節點數（node）總共有 305 個，且有 104 個樹葉
節點（leaf node），試求出分支度（degree of branch）為 1的節點數有多少個？（10 分）
二、已知一個二元樹（binary tree）的後序追蹤（postorder traversal）為 FEACGHBD，而
中序追蹤（inorder traversal）為 EFADCBGH，其中字母 A到H分別代表一個節點的
名稱。
請畫出此二元樹。（10 分）
請寫出此二元樹的前序追蹤（preorder traversal）。（5 分）
請寫出此二元樹的廣度優先走訪順序（breadth-first traversal）。（5 分）
三、給定一權重圖（weighted graph）如下：
試寫出下圖的相鄰矩陣（adjacency matrix）及相鄰串列（adjacency list）。（ 10 分）
請使用 Kruskal 演算法找出下圖的其一種最小生成樹（minimum spanning tree），
並寫出最小生成樹的邊之建構順序。（15 分）
四、今有八個數字： 6、12、7、9、15、10、4、11 儲存於陣列中，由不同演算法進行遞
增排序。
請按照合併排序法（merge sort）步驟，列出此八個數字的順序變化過程。（10 分）
請按照快速排序法（quick sort）步驟，列出此八個數字的順序變化過程。（10 分）
如果輸入 n筆資料時，請寫出這二種排序法之時間複雜度以及空間複雜度。（10 分）
五、請使用虛擬碼（pseudocode）或 C語言或 C++語言撰寫
程式片段。
以遞迴的呼叫方式寫出二元搜尋法（binary search）。（10 分）
根據所寫的虛擬碼或程式碼，寫出二元搜尋法之時間複雜度。（5 分）