試題評析 考點命中 年高上高普考 高分詳解 資料結構 資料結構應試者宜多加準備, 才能獲取佳績 高點第一題 : 本題考的是內插法搜尋的基本特性 第二題 : 本題測驗鏈結串列基本操作的做法 第三題 : 本題考的是一些特殊狀況的排序選擇 第四題 : 本題測驗最低成本伸展樹最重要的兩種演算法 第五題 : 本題測驗資料結構的設計能力, 必須利用 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), 因為當資料分佈不平均時, 會退化成與線性搜尋一樣 -- --
年高上高普考 高分詳解 二 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 分 ) 6 7 5 E D 9 5 9 8 A 7 6 B C -- --
年高上高普考 高分詳解 ( 一 )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, 這樣就可以要求 首節點陣列 高 4... 98 99 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 符號表示 -- --
年高上高普考 高分詳解 ( 三 ) 若是要在 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= -- 4 --
年高上高普考 高分詳解 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 = 7 6 4+8+ =4 (++) 5 9 4 8 4 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 ) -- 5 --