加載中. ..
PDF
100 年特種考試地方政府公務人員考試試題 代號：
等 別： 三等考試
類 科： 資訊處理
科 目： 資料結構
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
34280
一、給一規則的整數數列A={A0, A1, A2, ...}={1, 1, 1, 3, 5, 9, 17, 31, 57,…}。
試寫一遞迴函式（recursive function）計算An的數值。（10 分）
利用上述遞迴方法詳列計算A6 數值的過程。（10 分）
二、假設有一整數資料陣列 B[0..7]，裡面儲存 8個整數數值分別為{25, 57, 86, 37, 12,
92, 48, 33}。今欲對此陣列進行由小到大排序：
試寫出氣泡浮昇排序（bubble sort）演算法或函式。（10 分）
將排序過程中每一回合（iteration）陣列內容的變化情形寫出。（10 分）
三、假設鏈結串列（linked list）資料結構的宣告如下：
struct node {
char info;
struct node *next;
} *list;
試寫一函式（function）計算並回傳鏈結串列 list 內部節點（node）之數量。
（10 分）
試寫一函式（function）將鏈結串列 list 進行反轉（inverse）。（10 分）
四、依序輸入一組整數資料{25, 57, 86, 37, 12, 92, 48, 33}並建立出二元搜尋樹（binary
search tree）。
說明對二元搜尋樹（binary search tree）加入一筆資料的方法為何？（10 分）
請畫出所建立之二元搜尋樹（binary search tree）。（10 分）
五、給一個加權連通無向圖（weighted connected graph），所有邊線的加權值為正整數。
使用下列的貪婪演算法（Greedy algorithm）尋找從出發的節點 Start 到目的地節點
Goal 之最短路徑。
初始化集合 Path ={Start}
初始化集合 VisitedVertices ={Start}
如果 Start =Goal, 離開;否則,繼續第 4步驟
找出具有最小加權值的邊線 edge（Start, v）其中 v不在集合 VisitedVertices 內
將 {v} 加入集合 Path
將 {v} 加入集合 VisitedVertices
將Start 設為 v 並執行第 3步驟
請問是否可以正確找到最短路徑？（10 分）
請說明原因或理由。（需舉圖例說明理由，否則不予計分）（10 分）