Microsoft Word - 103高考-資料結構

Size: px

Start display at page:

Download "Microsoft Word - 103高考-資料結構"

附云
5 years ago
Views:

1 103 年公務人員高等考試三級考試試題類科 : 資訊處理科目 : 資料結構一給一個排序好的陣列 (Sorted Array) A[low high], 當我們要搜尋一個元素 X 是否在此陣列 A 中, 二元搜尋法 (Binary Search) 是檢查陣列的中間位置的元素 A[next], next=[(low+high)/2], 和 X 做比較, 並依比較結果作下列更新 Case: A[next]=X:return A[next]>X:highnext-1 A[next]<X:lownext+1 重複上述步驟搜尋更新的陣列 A[low high] 直到找到 X 或確認 X 不是在此陣列 A 中若我們設計一個新的搜尋法來修改二元搜尋法, 每次都是以下列方式選取 A[next] next low+ (high-low)*(x-a[low])/(a[high]-a[low]) 其他步驟都和二元搜尋相同請回答下列問題 : 新的搜尋法特色為何? 請說明之新的搜尋法在何種情形下, 會比二元搜尋的搜尋速度為佳? 請說明之新的搜尋法, 在最差的情形下, 它的執行時間複雜度為多少? 原因為何? 假設陣列 A 中有 n 個元素擬答 : 此新的搜尋法為內插搜尋法 (interpolation search), 改良自二分搜尋法 (binary search), 同樣都只能在資料已進行的情況下進行搜尋但是, 若在資料分布均勻時, 其效率是會比二分搜尋法還高的所謂分布均勻, 乃指資料的分佈是呈直線的, 因此任取 2 點計算得到的斜率應該都一樣, 故可由斜率公式推導出 next 值最有可能的位置內插搜尋法執行的快慢, 與鍵值在檔案中的分佈情況有決定性的關係, 因此在資料越平均分佈時會有最好的效果, 時間複雜度會優於 O(log2N), 例如 : 在資料並非分布均勻的最差情況下, 內插搜尋法則是需要進行 n 次比對才能夠找到資料, 因為每次搜尋筆數只排除一筆, 此時的效率就比二分搜尋法低上許多, 退化為循序搜尋, 時間複雜度為 O(n) 二 L 為一鏈結串列 (Linked List), 函數 Reverse(L) 是要求把在原來 L 的每個節點 (Node) 的地址指標 (Pointer), 更改為指向它在鏈結串列 L 中的前面一個節點請設計一個以疊代 (Iterative) 方式的程式來執行函數 Reverse(L) 的功能, 程式限制只能使用常數個 (constant) 額外空間 (External Memory), 可用程序語言 C C++ Java 或 Pseudocode, 寫出你的答案請先說明你的作法, 再寫出程式擬答 : 作法如下 : 先宣告三個額外指標 : current: 指向現行節點 previous: 指向現行節點之前一節點位置 forward: 指向現行節點之後一節點位置參考程式 Reverse() { list_pointer head,current,previous,forward; previous = NULL; current = head; /* 令目前節點指向第一個節點 */ 共 5 頁第 1 頁

2 forward = NULL; } /* 利用 while 將串列反轉 */ while(current!= NULL){ forward = current->next; current->next = previous; previous = current; current = forward; } head = previous; 三若只能使用下列 6 種方式排序 (Sorting):(a)Insertion Sort (b)radix Sort (c)merge Sort (d)counting Sort (e)heap Sort (f)quick Sort 在下列各情形下, 應選擇上述何種排序方法為最佳? 請說明原因 ( 每小題 5 分, 共 15 分 ) 只要將全部資料中的前 20 名最大值排序好, 並且主記憶體空間足夠只有少數資料在被已排序好的資料修改過, 需要重排序, 並且主記憶體空間足夠資料無明顯特性, 需要做第一次的排序, 並且主記憶體空間足夠擬答 : Heap Sort 如果採用 Max Heap, 則每次可在樹根獲得最大值, 可執行 20 次即可得到前 20 名最大值且依序輸出 Insertion Sort Insertion Sort 是一種簡單容易理解的排序演算法, 其概念是利用另一個數列來存放已排序部分, 逐一取出未排序數列中元素, 從已排序數列由後往前找到適當的位置插入, 因此在大多數資料已排序的狀況之下, 使用 Insertion Sort 可得到極佳的排序時間 O(n) Merge Sort 這六種排序法, 各有各的適合排序狀況, 在題目強調 " 資料無明顯特性 " 之前提下,Merge Heap 與 Quick 三種排序法的最佳與平均狀況所耗費的時間差不多, 但是 Merge Sort 為穩定排序, 即使 Merge Sort 需要較多的額外記憶體來處理, 但題目已指明主記憶體空間足夠, 因此選擇 Merge Sort 四如右的權重圖 (weighted graph) 共有 9 個節點 (vertices)19 條邊 (edges) 回答下列問題 : 請列出在運用 Kruskal's 演算法產生最小連結樹 (Minimum Spanning Tree) 中把邊納入最小連結樹的順序請列出運用 Prim's 演算法從 A 點開始產生最小連結樹, 把邊納入最小連結樹的順序設計一個 O(V) 的演算法, 判定在新增加一個 (x, y) 的邊到原圖形後, 是否要更新已經產生的最小連結樹擬答 : H-C,OK I-G,OK G-H,OK I-H, 迴圈, 捨棄共 5 頁第 2 頁

3 H-E,OK A-C,OK A-B,OK D-B,OK E-C, 迴圈, 捨棄 D-A, 迴圈, 捨棄 G-E, 迴圈, 捨棄 F-B,OK A, A-C, A-C-H, A-C-H-G, A-C-H-G-I, A-C-H-G-I-E A-C-G-H-I-E-B A-C-H-G-I-E-B-D A-C-H-G-I-E-B-D-F 演算法如下 Let e1=(x,y) the new edge added Find in T the shortest path from x to y if e1 is the most expensive edge in the cycle then T remains the MST else T is not the MST 五若處理的資料, 其數值均不同且已知均為 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 ) 時間內完成請說明設計的資料結構為何? 並解釋其執行時間為何滿足需求? 擬答 : 可以使用 AVL 樹來儲存資料,AVL-tree 定義如下 : 一棵空樹 (empty tree) 是高度平二元搜尋樹假使 T 不是空的二元搜尋樹,TL 和 TR 分別是此二元搜尋樹的左子樹和右子樹, 若符合下列兩個條件, 則稱 T 為高度平衡二元搜尋樹 : TL 和 TR 亦是高度平衡二元搜尋樹, hl-hr 1,hL 為左子樹的高度 ; 而 hr 是右子樹的高度 AVL 樹之搜尋刪除與插入資料的時間複雜度皆為 O(log n), 而列印全部排序資料則為 O(n), 可滿足題目需要討論最差情況之下之時間複雜度 : Insert(X):AVL 樹插入如同是未平衡的二元搜尋樹一樣, 將 X 值插入樹中成為樹葉, 接著自底部向上至 root 節點一路判別插入期間是否有成為不平衡的節點, 若有, 則進行旋轉來完成每次 AVL 旋轉都耗費固定的時間, 插入處理在整體上耗費 O(log Lx ) 時間 Delete(X): 從 AVL 樹中刪除 X 的做法為將刪除的 X 節點向下旋轉成為葉節點, 接著直接移除這個葉節點來完成因為在旋轉成葉節點期間最多有 log Lx 個節點被旋轉, 而每次 AVL 旋轉耗費固定的時間, 刪除處理在整體上耗費 O(log Lx ) 時間 List(X): 若要將資料依序列印, 依照二元搜尋樹的特性, 採用中序追蹤此 AVL 樹, 即可得到共 5 頁第 3 頁

4 結果, 中序走訪時間複雜度為 O( Lx ) 如上述所討論,AVL 樹可滿足題目要求六若 G=(U,E) 為一權重圖 (weighted graph), 每條邊的權重均不為負數, 則單源最短路徑問題 (Single Source Shortest Path Problem) 可以用著名的 Dijkstra 演算法求得, 回答下列問題 : 說明 Dijkstra 演算法的主要觀念 Dijkstra 演算法在最差情況下 (Worst Case Analysis), 下列三個功能 Insert Delete Decrease_Key 各自需要執行的次數, 可用 Big-Oh 符號表示若是要在 O( E + V log V) 最差情況分析下的時間內執行 Dijkstra 演算法, 請問該選擇使用那種資料結構, 並說明其原因擬答 : 首先以某一節點當作出發點, 在與其相連且尚未被選取的節點裡, 選擇加入離出發點距離最短的節點, 並且透過新增的節點修正並且更新到達其他節點的距離如此重覆加入新節點, 直到所有的節點都被加入為止 Insert:O(1);Delete:O(V logv);decrease_key(1) 如使用連接矩陣, 時間複雜度為 O(V 2 ), 可使用 Fibonacci heap 來實做以降低時間複雜度七下面二小題各有一段程式, 其執行的時間是以執行 sum++ 的次數計算, 請用 Θ-notation 表示其執行時間, 並說明其理由 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++; 擬答 : Θ(n 2 ) 首先將迴圈執行狀況列表 i 值 j 值 sum++ 次數由上表得知, 當 i 值為 1 時, 執行一次,i 值為 2 時, 執行兩次, 因此 sum++ 執行次數為 (2n-1) = ((2n-1)+1)*(2n-1)/2=2n 2 -n 由 Θ notation 可得到為 Θ(n 2 ) Θ(n 4 ) 比照上小題, 將迴圈執行狀況列表 : i 值 j 值 k 值判別式成立 - - n y y - n n n y y y n n n n n n n n n y y y y y y n n n n n n n n n n n n n n n sum++ 次數此題較為特別的地方有個判別式 :if (j%i==1), 找出 i 與 j 的關係式即可解決此小題 i=2,j=3, 次數 2 次共 5 頁第 4 頁

5 i=3,j=4 與 7, 次數 3+6=9 次 i=4,j=5 9 與 13, 次數 =24 次 i i=2n-1,j=ix+1,x=1~i-1, 次數變為 x 2n 1 因此 sum++ 執行次數為 i 2 i i ( i 1) / 2 由 Θ notation 可得到為 Θ(n 4 ) 1 1 ix 次共 5 頁第 5 頁

Microsoft Word - K34資料結構_題+解+評OK_.doc

Microsoft Word - K34資料結構_題+解+評OK_.doc 試題評析考點命中年高上高普考高分詳解資料結構資料結構應試者宜多加準備, 才能獲取佳績高點第一題 : 本題考的是內插法搜尋的基本特性第二題 : 本題測驗鏈結串列基本操作的做法第三題 : 本題考的是一些特殊狀況的排序選擇第四題 : 本題測驗最低成本伸展樹最重要的兩種演算法第五題 : 本題測驗資料結構的設計能力, 必須利用 AVL-tree, 以及一點組合能力即可, 算是簡單的設計問題