阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
103年 - 103 高等考試_三級_資訊處理:資料結構#17891
> 申論題
題組內容
四、如右的權重圖(weighted graph)共有 9 個節點(vertices)19 條邊(edges),回答下 列問題:
請列出運用 Prim’s 演算法從 A 點開始產生最小 連結樹,把邊納入最小連結樹的順序。(4 分)
相關申論題
新的搜尋法特色為何?請說明之。
#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
只要將全部資料中的前 20 名最大值排序好,並且主記憶體空間足夠。
#15571
只有少數資料在被已排序好的資料修改過,需要重排序,並且主記憶體空間足夠。
#15572
資料無明顯特性,需要做第一次的排序,並且主記憶體空間足夠。
#15573
請列出在運用 Kruskal’s 演算法產生最小連結樹 (Minimum Spanning Tree)中把邊納入最小連結 樹的順序。(3 分)
#15574
設計一個 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
相關試卷
114年 - 114 地方政府公務特種考試_三等_資訊處理:資料結構#134706
114年 · #134706
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
114年 · #133251
114年 - 114 高等考試_三級_資訊處理:資料結構#128753
114年 · #128753
114年 - 114 關務特種考試_三等_資訊處理(選試英文):資料結構#126563
114年 · #126563
114年 - 114 身心障礙特種考試_三等_資訊處理:資料結構#126562
114年 · #126562
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理:資料結構#124511
113年 · #124511
113年 - 113 高等考試_三級_資訊處理:資料結構#121217
113年 · #121217
113年 - 113 關務特種考試_三等_資訊處理(選試英文):資料結構#119489
113年 · #119489
112年 - 112 地方政府特種考試_三等_資訊處理:資料結構#118368
112年 · #118368
112年 - 112 公務升官等考試_薦任_資訊處理:資料結構#117327
112年 · #117327