100年特種考試地方政府公務人員三等考試 資料結構

給一規則的整數數列
(1) 試寫一遞迴函式（recursive function）計算An 的數值。
(2) 利用上述遞迴方法詳列計算A₆數值的過程。

假設有一整數資料陣列 B[0..7]，裡面儲存8 個整數數值分別為{25, 57, 86,
37, 12, 92, 48, 33}。今欲對此陣列進行由小到大排序：
(1) 試寫出氣泡浮昇排序（bubble sort）演算法或函式。
(2) 將排序過程中每一回合（iteration）陣列內容的變化情形寫出。

假設鏈結串列（linked list）資料結構的宣告如下：
struct node {
char info;
struct node *next;
} *list;
(1) 試寫一函式（function）計算並回傳鏈結串列list 內部節點（node）之
數量。
(2) 試寫一函式（function）將鏈結串列list 進行反轉（inverse）。

依序輸入一組整數資料{25, 57, 86, 37, 12, 92, 48, 33}並建立出二元搜尋樹
（binary search tree）。
(1) 說明對二元搜尋樹（binary search tree）加入一筆資料的方法為何？
(2) 請畫出所建立之二元搜尋樹（binary search tree）。

給一個加權連通無向圖（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 步驟
(1) 請問是否可以正確找到最短路徑？
(2) 請說明原因或理由。（需舉圖例說明理由，否則不予計分）