資訊處理 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 分）

有一個N×N 的上三角矩陣，每個元素占一個Byte。 試以最少的記憶體儲存之，請說明應用何種資料結構？（5 分） 總共用多少記憶體空間？（5 分） 若矩陣第一個元素（0,0）在位址S，請分別以Row-Major 及Column-Major Ordering 寫出矩陣任意元素（i, j）所在位址的表示式。（10 分）

給一個排序好的陣列（Sorted Array）A[low...high]，當我們要搜尋一個元素X 是否 在此陣列A 中，二元搜尋法（Binary Search）是檢查陣列的中間位置的元素 A[next], next=(low+high)/2，和X 做比較，並依比較結果作下列更新。 Case： A[next]＝X：return A[next]＞X：high  next-1 A[next]＜X：low  next+1 重複上述步驟搜尋更新的陣列A[low...high]直到找到X 或確認X 不是在此陣列A 中。 若我們設計一個新的搜尋法來修改二元搜尋法，每次都是以下列方式選取A[next]。 next←low+(high-low) * (X-A[low])／(A[high]-A[low]) 其他步驟都和二元搜尋相同。請回答下列問題：（每小題5 分，共15 分）  新的搜尋法特色為何？請說明之。  新的搜尋法在何種情形下，會比二元搜尋的搜尋速度為佳？請說明之。  新的搜尋法，在最差的情況下，它的執行時間複雜度為多少？原因為何？假設陣 列A 中有n 個元素。

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

請將下列運算式由中序（Infix）改為後序（Postfix）及前序（Prefix）表示法， （A-B）^（X+D）^（Y-4%H）*G-6/（F+2）+C。 其中 ^為指數運算符號、%為取餘數運算符號。（10 分）

L 為一鏈結串列（Linked List），函數Reverse(L)是要求把在原來L 的每個節點（Node） 的地址指標（Pointer），更改為指向它在鏈結串列L 中的前面一個節點。請設計一 個以疊代（Iterative）方式的程式來執行函數Reverse(L)的功能，程式限制只能使用 常數個（constant）額外空間（External Memory），可用程式語言C、C++、Java 或 Pseudocode，寫出你的答案。請先說明你的作法，再寫出程式。（15 分）

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 分）

已知有一個二元樹的前序搜尋（Preorder）結果為“ABDGHCE”，且其後序搜尋 （Postorder）結果為“GHDBECA”。請問由前述二個結果，是否可以得到唯一的 二元樹（4 分）？前小題若為是，請畫出此唯一的二元樹；否者，請畫出二個二 元樹，可得出具有前述前序搜尋與後序搜尋之結果（6 分）。

若只能使用下列6 種方式排序（Sorting）：(a)Insertion Sort (b)Radix Sort (c)Merge Sort (d)Counting Sort (e)Heap Sort (f)Quick Sort。在下列各情形下，應選擇上述何種 排序方法為最佳？請說明原因。（每小題5 分，共15 分）  只要將全部資料中的前20 名最大值排序好，並且主記憶體空間足夠。  只有少數資料在被已排序好的資料修改過，需要重排序，並且主記憶體空間足夠。  資料無明顯特性，需要做第一次的排序，並且主記憶體空間足夠。

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

有一組原始的整數序列為56, 18, 79, 7, 42, 96, 35, 66，請分別以Insertion sort 及 Quick sort 的方法寫出將此一數列由小到大的排序過程。注意：是寫出排序的過程， 不只是排序結果。（20 分）

如右的權重圖（weighted graph）共有9 個節點（vertices）19 條邊（edges），回答下 列問題：  請列出在運用Kruskal’s 演算法產生最小連結樹 （Minimum Spanning Tree）中把邊納入最小連結 樹的順序。（3 分）  請列出運用Prim’s 演算法從A 點開始產生最小 連結樹，把邊納入最小連結樹的順序。（4 分）  設計一個O(V)的演算法，判定在新增加一個 (x,y)的邊到原圖形後，是否要更新已經產生的最 小連結樹。（8 分） 12 A B C D F H I G E 13 16 8 7 6 9 15 19 10 3 11 17 18 2 14 4

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

請寫出下列圖形結構的相鄰串列（Adjacent List）（串列順序應依節點編號由小至大 表示）（6 分）。並請依此相鄰串列畫出以S5 為起點之DFS 展開樹（DFS Spanning Tree）及BFS 展開樹（BFS Spanning Tree）（14 分）。 1 0 3 年公務人員特種考試警察人員考試 103年公務人員特種考試一般警察人員考試 103年特種考試交通事業鐵路人員考試試題 全一張 （背面）

1 103年公務人員高等考試三級考試試題 全一張 （背面） 五、若處理的資料，其數值均不同且已知均為1 到100 之間的整數或小數。若K≦X＜ K+1，集合Lx 代表數值在[K,K-1]間全部資料，1≦K≦99, K 為整數，資料結構支援 下列功能。 Insert(X)：增加X，若X 不存在Lx 中。 Delete(X)：移除X，若X 存在Lx 中。 List(X)：將Lx 中的資料全部依序印出。 設計一資料結構滿足在最差情況的條件分析（Worst Case Analysis），每個功能的執 行時間要求為：Insert(X) and Delete(X)須在O(log|Lx|)時間內完成，List(X)則須在 O(|Lx|)時間內完成。請說明設計的資料結構為何？並解釋其執行時間為何滿足需求？ （15 分）

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

若G=(U,E)為一權重圖（weighted graph），每條邊的權重均不為負數，則單源最短 路徑問題（Single Source Shortest Path Problem）可以用著名的Dijkstra 演算法求得， 回答下列問題：（每小題5 分，共15 分）  說明Dijkstra 演算法的主要觀念。  Dijkstra 演算法在最差情況下（Worst Case Analysis），下列三個功能Insert、 Delete、Decrease_Key 各自需要執行的次數，可用Big-Oh 符號表示。  若是要在O(|E|+|V|log|V|)最差情況分析下的時間內執行Dijkstra 演算法，請問該 選擇使用那種資料結構，並說明其原因。

已知使用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 };

下面二小題各有一段程式，其執行的時間是以執行sum++的次數計算，請用 Θ-notation 表示其執行時間，並說明其理由。（每小題5 分，共10 分）  sum=0 for(i=0; i＜2*n; i++) for(j=0; j<i; j++) sum++;  sum=0 for(i=1; i＜2*n; i++) for(j=1; j＜i*i; j++) for(k=1; k<j; k++) if(j%i==1) sum++;