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

Size: px

Start display at page:

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

锄柏
6 years ago
Views:

1 試題評析考點命中年高上高普考高分詳解資料結構資料結構應試者宜多加準備, 才能獲取佳績高點第一題 : 本題考的是內插法搜尋的基本特性第二題 : 本題測驗鏈結串列基本操作的做法第三題 : 本題考的是一些特殊狀況的排序選擇第四題 : 本題測驗最低成本伸展樹最重要的兩種演算法第五題 : 本題測驗資料結構的設計能力, 必須利用 AVL-tree, 以及一點組合能力即可, 算是簡單的設計問題第六題 : 測驗考生對於有名的單起點最短路徑演算法, 是否有實際完整的了解, 是否清楚所需要的資料結構為何第七題 : 本題測驗考生對於程式的頻率計次計算的觀念與實際計算能力綜觀本次高考資料結構試題特性, 有兩個主要的特點, 一是題目的份量實在不算少, 因此答題速度必須掌握好, 如果先作答的題目耗費太多時間, 可能導致答不完 ; 二是題目有部分簡單, 有部分較難些, 以命題角度而言, 是相當不錯的一份試題, 可以鑑別出考生的程度由此可見, 未來第一題 : 資料結構高點出版, 王致強編撰, 頁 -~-5 頁, 內插搜尋法第二題 : 資料結構高點出版, 王致強編撰, 頁 -6 頁, 將單鏈非循環串列的反轉第三題 : 資料結構高點出版, 王致強編撰, 頁 9-7 頁, 排序綜合討論第四題 : 資料結構高點出版, 王致強編撰, 頁 8-4~8-4 頁,Kruskal's Algorithm 與 Prim's 演算法第五題 : 資料結構高點出版, 王致強編撰, 頁 -~-5 頁, 第 -5 節 AVL-trees 第六題 : 資料結構高點出版, 王致強編撰, 頁 8-6~8-6 頁,Dijkstra 演算法第七題 : 資料結構高點出版, 王致強編撰, 頁 -7 頁, 精選範例 4 高上一給一個排序好的陣列 (Sorted Array)A[low high], 當我們要搜尋一個元素 X 是否在此陣列 A 中, 二元搜尋法 (Binary Search ) 是檢查陣列的中間位置的元素 A[next], next=[(low+high)/], 和 X 做比較, 並依比較結果作下列更新 Case: A[next]=X : return A[next]>X : high next-l A[next]<X : low next+ 重複上述步驟搜尋更新的陣列 A[low high] 直到找到 X 或確認 X 不是在此陣列 A 中若我們設計一個新的搜尋法來修改二元搜尋法, 每次都是以下列方式選取 A[next] next low+[(high-low) * (X-A [low])/(a[high] -A[low])] 其他步驟都和二元搜尋相同請回答下列問題 :( 每小題 5 分, 共 5 分 ) ( 一 ) 新的搜尋法特色為何? 請說明之 ( 二 ) 新的搜尋法在何種情形下, 會比二元搜尋的搜尋速度為佳? 請說明之 ( 三 ) 新的搜尋法, 在最差的情況下, 它的執行時間複雜度為多少? 原因為何? 假設陣列 A 中有 n 個元素 ( 一 ) 此一新的搜尋法就是內插搜尋法, 使用內插法的公式, 計算要搜尋的資料 X 可能會在那一個位置, 再加以比較, 若未搜尋到, 就判斷往前或是往後搜尋 ( 二 ) 在資料平均分佈時, 平均搜尋時間為 O(loglogn), 會比二元搜尋法的 O(logn) 來得好 ( 三 ) 在最差的情況下, 它的執行時間複雜度為 O(n), 因為當資料分佈不平均時, 會退化成與線性搜尋一樣 -- --

2 年高上高普考高分詳解二 L 為一鏈結串列 (Linked List), 函數 Reverse(L) 是要求把在原來 L 的每個節點 (Node) 的地址指標 (Pointer), 更改為指向它在鏈結串列 L 中的前面一個節點請設計一個以疊代 (Iterative) 方式的程式來執行函數 Reverse(L) 的功能, 程式限制只能使用常數個 (constant) 額外空間 (External Memory), 可用程式語言 C C++ Java 或 Pseudocode, 寫出你的答案請先說明你的作法, 再寫出程式 (5 分 ) 除了 L 之外再增加兩個指標變數, 由串列開頭逐一將節點的鏈結反轉 () NodePtr Reverse(NodePtr L) () { () NodePtr p, q; (4) p=null; (5) while (L!=NULL) (6) { q=p; p=l; L=L->link; p->link=q; } (7) return p; (8) } 高點三若只能使用下列 6 種方式排序 (Sorting): (a)insertion Sort (b)radix Sort (c)merge Sort (d)counting Sort (e)heap Sort (f)quick Sort 在下列各情形下, 應選擇上述何種排序方法為最佳? 請說明原因 ( 每小題 5 分, 共 5 分 ) ( 一 ) 只要將全部資料中的前名最大值排序好, 並且主記憶體空間足夠 ( 二 ) 只有少數資料在被已排序好的資料修改過, 需要重排序, 並且主記憶體空間足夠 ( 三 ) 資料無明顯特性, 需要做第一次的排序, 並且主記憶體空間足夠高上 ( 一 )Heap Sort: 若只要排序前名最大的資料, 可以採用 Heap Sort, 每次從未排好的部分, 選擇出最大的資料, 並交換到前面的位置在每次要選出最大的一項資料, 使用 Max Heap 都只需要 O(logn) 的時間, 故總時間為最少 ( 二 )Insertion Sort: 在插入資料時, 只有少數未排序好的資料需要花 O(n) 的時間, 其餘的每項資料都只要 O() 時間, 故總時間為最節省 ( 三 )Quick Sort:Quick Sort 在普遍的狀況之下, 平均時間為最佳的 O(nlogn) 說明 :Insertion Sort 時間為 O(n), 複雜度較高 ;Radix Sort 比較適合資料很平均分佈的狀況, 才能有 O(kn)=O(nlogn) 的時間 (k 為 key 的位數 );Merge Sort 的問題則為搬動次數過多 ;Counting Sort 比較適合,key 的範圍較小且重覆性較高的狀況 ;Heap Sort 的時間複雜度 O(nlogn), 與 Quick Sort 一樣, 但是 Overhead 較高, 會使實際執行時間比較長故資料在沒有特定條件與特性的狀況之下, 選擇 Quick Sort 四如右的權重圖 (weighted graph ) 共有 9 個節點 (vertices)9 條邊 (edges), 回答下列問題 : F ( 一 ) 請列出在運用 Kruskal's 演算法產生最小連結樹 8 4 (Minimum Spanning Tree) 中把邊納入最小連結樹的順序 ( 分 ) I G ( 二 ) 請列出運用 Prim's 演算法從 A 點開始產生最小連結樹, 把邊納入最小連結樹的順序 (4 分 ) ( 三 ) 設計一個 O(V) 的演算法, 判定在新增加一個 (x,y) 4 H 的邊到原圖形後, 是否要更新已經產生的最小連結樹 (8 分 ) E D A 7 6 B C -- --

3 年高上高普考高分詳解 ( 一 )Kruskal's 演算法的加入邊的順序依序為 (H,C),(I,G),(G,H),(E,H),(A,C),(A,B),(D,B),(B,F) ( 二 )Prim's 演算法的加入邊的順序依序為 (A,C),(H,C),(G,H),(I,G),(E,H),(A,B),(D,B),(B,F) ( 三 ) 在連結樹上加入一個邊, 必定會產生迴圈, 在此一新產生的迴圈上, 找出最大的一個邊, 若此一最大的邊就新加入的邊, 則最小連結樹與原先相同, 不用更新 ; 否則, 以新加入的邊, 取代掉迴圈上最大的邊, 即可更新最小連結樹因為迴圈中的邊個數 V, 故處理的時間為 O(V) 高點五若處理的資料, 其數值均不同且已知均為到之間的整數或小數若 K X K, 集合 Lx 代表數值在 [K,K-l] 間全部資料, 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 ) 時間內完成請說明設計的資料結構為何? 並解釋其執行時間為何滿足需求?(5 分 ) ( 一 ) 使用如下圖之資料結構設計, 每一個集合 Lx 都各自建立一棵 AVL-tree, 再使用一個首節點陣列分別指向這些 AVL-tree 的 root, 這樣就可以要求首節點陣列高 AVL-Tree 集合 L AVL-Tree 集合 L AVL-Tree 集合 L 上AVL-Tree 99 集合 L99 ( 二 ) 最差情況的條件分析.Insert(x): 由首節點陣列, 找到 Lx 的 AVL-tree root, 再將資料 x 插入樹中, 時間 O(log Lx ).Detete(X): 由首節點陣列, 找到 Lx 的 AVL-tree root, 再將 x 由 AVL-tree 刪除, 時間亦為 O(log Lx ).List(X): 要將 Lx 中的資料全部依序印出, 也是由首節點陣列, 找到 Lx 的 AVL-tree root, 再對 AVL-tree 進行中序走訪, 時間 O( Lx ) 六若 G=(U,E) 為一權重圖 (weighted graph), 每條邊的權重均不為負數, 則單源最短路徑問題 (Single Source Shortest Path Problem) 可以用著名的 Dijkstra 演算法求得, 回答下列問題 :( 每小題 5 分, 共 5 分 ) ( 一 ) 說明 Dijkstra 演算法的主要觀念 ( 二 )Dijkstra 演算法在是差情況下 (Worst Case Analysis), 下列三個功能 Insert Delete Decrease_Key 各自需要執行的次數, 可用 Big-Oh 符號表示 -- --

4 年高上高普考高分詳解 ( 三 ) 若是要在 O( E + V log V ) 最差情況分析下的時間內執行 Dijkstra 演算法, 請問該選擇使用那種資料結構, 並說明其原因 dist[w] min{dist[w],dist[u] cos t[u, w]} 高點 ( 一 )Dijkstra 演算法的觀念 : 由最近的 vertex 開始, 依照非遞減順序找出每個 vertices 的最短路徑使用下列資料 : ()cost[u,v]: 邊 (u,v) 的成本 ()S 為已經找到最短路徑的頂點集合 ()dist[w]: 由起點 v 到 w, 目前已找到的最短路徑長度路徑上所經過的皆為 S 中的 vertices (4)pred[w]: 記錄由起點 v 到頂點 w 最短路徑上,w 的直接前行者 (immediate predecessor) 演算法運算原則 () 由 V-S 中選擇一個 dist 值最小的頂點 u () 將頂點 u 加入 S () 檢查每一個 (u,w) 邊, 若 w S, 則計算 ( 二 )Insert 需要 O( V ) 次 ;Delete 也需要 O( V ) 次 ;Decrease_Key 需要 O( E ) 次 ( 三 ) 應選擇 Fibonacci-Heaps 為最優, 其每次 Insert 的時間為 O(); 每次 Delete(Delete-min) 的時間為 O(log V ); 而每次 Decrease_Key 的時間為 O() 故總時間為 O( V ) O()+O( V ) O(log V )+O( E ) O()=O( V log V + E ) 高上七下面二小題各有一段程式, 其執行的時間是以執行 sum++ 的次數計算, 請用 -notation 表示其執行時間, 並說明其理由 ( 每小題 5 分, 共分 ) ( 一 )sum=o for(i=o; i<*n; i++) for(j=o; j<i; j++) ( 二 )sum=o for(i=; i<*n; i++) for(j=; j<i*i; j++) for(k=l; k<j; k++) if(j%i==l) ( 一 )sum++ 的執行次數如下表整理 i j 次數 -,,, n-,,,...,n- n- (n )(n) 總計 :... (n ) (n ) ( 二 ) 本題 sum++ 的執行次數與下面程式相同, 使用下面程式可以讓計算簡化一些 sum=

5 年高上高普考高分詳解 for(i=l; i<*n; i++) for(j=l; j<i*i; j++) 高if(j%i==) for(k=l;k<j;k++) 故 sum++ 的執行次數如下表整理 : 總計 : i j 次數 (=j- 次 ) 部份總和點 - = () = +6= (+) 4 = =4 (++) = n n- n- 4n- 4n = (n ) (n-)(n-)+ (n-)(n-) (i) (i ) (i) (n ) n 4 i 高上(n-)+...+(n-)(n-) =(n-) ( (n-)) (n ) (n )

Microsoft Word - 103高考-資料結構

Microsoft Word - 103高考-資料結構 103 年公務人員高等考試三級考試試題類科 : 資訊處理科目 : 資料結構一給一個排序好的陣列 (Sorted Array) A[low high], 當我們要搜尋一個元素 X 是否在此陣列 A 中, 二元搜尋法 (Binary Search) 是檢查陣列的中間位置的元素 A[next], next=[(low+high)/2], 和 X 做比較, 並依比較結果作下列更新 Case: A[next]=X:return