oklp16>试卷(2014/11/16)

公職◆資料結構題庫 下載題庫

103 年 - 103高等考試三級資訊處理資料結構#17891 

选择:0题,非选:15题
立即測驗 
我要補題 回報試卷錯誤 試卷下載

【非選題】

一、給一個排序好的陣列(Sorted Array)A[low...high],當我們要搜尋一個元素 X 是否 在此陣列 A 中,二元搜尋法(Binary Search)是檢查陣列的中間位置的元素 A[next], next =,和 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+ 其他步驟都和二元搜尋相同。請回答下列問題:(每小題 5 分,共 15 分)

【題組】 新的搜尋法特色為何?請說明之。

#15567
編輯私有筆記

【非選題】【題組】新的搜尋法在何種情形下,會比二元搜尋的搜尋速度為佳?請說明之。

#15568
編輯私有筆記

【非選題】【題組】新的搜尋法,在最差的情況下,它的執行時間複雜度為多少?原因為何?假設陣 列 A 中有 n 個元素。

#15569
編輯私有筆記

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

#15570
編輯私有筆記

【非選題】

三、若只能使用下列 6 種方式排序(Sorting):(a)Insertion Sort (b)Radix Sort (c)Merge Sort (d)Counting Sort (e)Heap Sort (f)Quick Sort。在下列各情形下,應選擇上述何種 排序方法為最佳?請說明原因。(每小題 5 分,共 15 分)

【題組】 只要將全部資料中的前 20 名最大值排序好,並且主記憶體空間足夠。

#15571
編輯私有筆記

【非選題】【題組】只有少數資料在被已排序好的資料修改過,需要重排序,並且主記憶體空間足夠。

#15572
編輯私有筆記

【非選題】【題組】資料無明顯特性,需要做第一次的排序,並且主記憶體空間足夠。

#15573
編輯私有筆記

【非選題】

四、如右的權重圖(weighted graph)共有 9 個節點(vertices)19 條邊(edges),回答下 列問題:

【題組】 請列出在運用 Kruskal’s 演算法產生最小連結樹 (Minimum Spanning Tree)中把邊納入最小連結 樹的順序。(3 分)

#15574
編輯私有筆記
1F
許庭瑜 國二下 (2015/02/27 16:22):
C H G I A D B E F

【非選題】【題組】請列出運用 Prim’s 演算法從 A 點開始產生最小 連結樹,把邊納入最小連結樹的順序。(4 分)

#15575
編輯私有筆記

【非選題】【題組】設計一個 O(V)的演算法,判定在新增加一個 (x,y)的邊到原圖形後,是否要更新已經產生的最 小連結樹。(8 分)

#15576
編輯私有筆記

【非選題】

五、若處理的資料,其數值均不同且已知均為 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 分)

#15577
編輯私有筆記

【非選題】

六、若 G=(U,E)為一權重圖(weighted graph),每條邊的權重均不為負數,則單源最短 路徑問題(Single Source Shortest Path Problem)可以用著名的 Dijkstra 演算法求得, 回答下列問題:(每小題 5 分,共 15 分)

【題組】 說明 Dijkstra 演算法的主要觀念。

#15578
編輯私有筆記

【非選題】【題組】Dijkstra 演算法在最差情況下(Worst Case Analysis),下列三個功能 Insert、 Delete、Decrease_Key 各自需要執行的次數,可用 Big-Oh 符號表示。

#15579
編輯私有筆記

【非選題】【題組】若是要在 O(|E|+|V|log |V|)最差情況分析下的時間內執行 Dijkstra 演算法,請問該 選擇使用那種資料結構,並說明其原因。

#15580
編輯私有筆記

【非選題】

七、下面二小題各有一段程式,其執行的時間是以執行 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++; 

#15581
編輯私有筆記