給一個排序好的陣列(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]
next←low+[(high-low)∗(X-A[low])/(A[high]-A[low])]
其他步驟都和二元搜尋相同。請回答下列問題:
(一)新的搜尋法特色為何?請說明之。
(二)新的搜尋法在何種情形下,會比二元搜尋的搜尋速度為佳?請說明之。
(三)新的搜尋法,在最差的情況下,它的執行時間複雜度為多少?原因為何?假設陣列A中有n個元素。
L為一鏈結串列(Linked List),函數Reverse(L)是要求把在原來L的每個節點(Node)的地址指標(Pointer),更改為指向它在鏈結串列L中的前面一個節點。請設計一個以疊代(Iterative)方式的程式來執行函數Reverse(L)的功能,程式限制只能使用常數個(constant)額外空間(External Memory),可用程式語言C、C++、Java或Pseudocode,寫出你的答案。請先說明你的作法,再寫出程式。
若只能使用下列6種方式排序(Sorting):(a)Insertion Sort (b)Radix Sort (c)Merge Sort (d)Counting Sort (e)Heap Sort (f)Quick Sort。在下列各情形下,應選擇上述何種排序方法為最佳?請說明原因。(一)只要將全部資料中的前20名最大值排序好,並且主記憶體空間足夠。
(二)只有少數資料在被已排序好的資料修改過,需要重排序,並且主記憶體空間足夠。
(三)資料無明顯特徵,需要做第一次的排序,並且主記憶體空間足夠。
如右的權重圖(weighted graph)共有9個節點(vertices)19條邊(edges),回答下列問題:
(一)請列出在運用 Kruskal's 演算法產生最小連結樹(Minimum Spanning Tree)中把邊納入最小連結樹的排序。
(二)請列出運用 Prim's 演算法從A點開始產生最小連結樹,把邊納入最小連結樹的順序。
(三)設計一個O(V)的演算法,判定在新增加一個(x,y)的邊到原圖形後,是否要更新已經產生的最小連結樹。
若處理的資料,其數值均不同且已知均為1到100之間的整數或小數。若K≦X?K+1,集合Lx代表數值在[K,K-1]間全部資料,1≦K≦99,K為整數,資料結構支援下列功能。
1. Insert(X):增加X,若X不存在Lx中。
2. Delete(X):移除X,若X存在Lx中。
3. List(X):將Lx中的資料全部依序印出。
設計一資料結構滿足在最差情況的條件分析(Worst Case Analysis),每個功能的執行時間要求為:Insert(X) and Delete(X)須在 O(log|Lx|)時間內完成,List(X)則須在O(|Lx|)時間內完成。請說明設計的資料結構為何?並解釋其執行時間為何滿足需求?
若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演算法,請問該選擇使用那種資料結構,並說明其原因。
下面二小題各有一段程式,其執行的時間是以執行sum++的次數計算,請用Θ-notation表示其執行時間,並說明其理由。
可觀看題目詳解,並提供模擬測驗!(免費會員無法觀看研究所試題解答)