資訊處理 103 年資料結構考古題

有一整數數列 f(n)=2*f(n−1)−f(n−2)+f(n−3), 3≤n, f(0)=0, f(1)=1, f(2)=2。 ㈠請使用C 或Java 語言，寫一非遞迴（non-recursive）副程式，此副程式輸入為一 整數參數3≤i，回傳此數列f(i)的數值。（12 分） ㈡請計算f(10)的數值。（8 分）

一個圖形（graph）包含五個頂點（vertex），V1, V2, …, V5，其鄰接矩陣（adjacency matrix） A= 。 ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ ∞ ∞ ∞ ∞ 0

2 5 3 0 6 7 2 6 0 1 3 5 7 1 0 1 3 1 0 ㈠請使用Floyd 的方法，計算此圖形的最短路徑長度矩陣（shortest path length matrix），來表示任兩頂點間最短路徑長度。（10 分） ㈡請使用Prim 的方法，繪出此圖形的最小成本擴張樹（minimum cost spanning tree）。（5 分） ㈢在任一圖形中，兩頂點在此圖形的最小成本擴張樹上的路徑，是否為這兩個頂點 在此圖形上的最短路徑，請舉例說明。（5 分） 三、㈠請繪出一二元樹來表示運算式（expression）–a+b/(c–d)–a*b/c+d。（8 分） ㈡請列出此二元樹的後序走訪（postorder traversal）、深度優先走訪（depth-first search traversal）及廣度優先走訪（breadth-first search traversal）。（12 分）

請使用C 或Java 語言寫一副程式void FindMinMax(int [] A, int Min, int Max)，此副 程式對一個長度為10 的整數陣列A[0:9]，最多花費15 次的數值比較運算，尋找陣 列中的最小值及最大值，並分別存入Min 及Max。（20 分） （注意：請加註解說明程式碼作法）

㈠陣列（array）、鏈結串列（linked list）是常見的線性資料結構（linear data structure）。請列舉兩種非線性的資料結構（non-linear data structure）。（8 分） ㈡在巨量資料（big data）分析中，何謂結構化資料（structured data）？請舉例 說明（6 分）；何謂非結構化資料（unstructured data）？請舉例說明（6 分）。

請推算下圖中，由節點 S 到其他各點的最短路徑長度以及路徑所需經過的節點。 （10 分）

已知使用Linked List 為Stack 的類別（Class）宣告如下，請寫出其Delete（Pop） 的函式（Functions）。（10 分） s x w t v y z u 1 1 1 1 1 1 1 10 10 10 10 10 10 template <class T> class Node { friend LinkedStack<T>; private : T data; Node<T> *link; }; template <class T> class LinkedStack { public : LinkedStack() {top = 0;} ~LinkedStack(); bool IsEmpty() const {return top == 0;} bool IsFull() const ; T Top() const ; LinkedStack<T>& Add(const T& x); LinkedStack<T>& Delete(T& x); private : Node<T> *top; // pointer to top node };