阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
114年 - 114 公務升官等考試_薦任_資訊處理:資料結構#133251
> 申論題
題組內容
五、下圖為一有向圖(Directed Graph)G。請完成下列各題:
(三)從節點 a 開始,寫出廣度優先搜尋(Breadth-First Search, BFS)的節點拜訪順序。
相關申論題
(一)使用遞迴方法(Recursion)撰寫虛擬碼,計算第 n 項的費伯納西數。 (8 分)
#555982
(二)使用動態規劃方法(Dynamic Programming)撰寫虛擬碼,透過自底向 上(Bottom-up)的方式計算第 n 項的費伯納西數。(8 分)
#555983
(三)比較兩個方法的時間複雜度(Time Complexity)。(6 分)
#555984
二、已知 B+-tree 的階數(Order)為 m = 3。葉節點至多可存放 2 個鍵值,至 少須存放 1 個鍵值;內部節點至多可有 3 個子節點,至少須有 2 個子節 點。當節點因插入而溢位時,規定葉節點分裂時將右子節點之第一個鍵 值提升至父節點,內部節點分裂時則將中間鍵值提升至父節點。請完成 下列各題: (一)依序插入 17、5、12、23、7、19、3、30 等 8 個鍵值以建構 B+-tree。 請逐步說明並繪製每次插入後之樹形結構。
#555985
(二)承接(一)之結果,依序刪除 7、23 與 5 等三個鍵值。刪除過程中若需借 值時,一律自右兄弟節點借取;若無法借值,則與左兄弟節點合併。 請逐步說明並繪製每次刪除鍵值後之樹形結構。(6 分)
#555986
(三)承接(一)之結果,說明在該 B+-tree 中搜尋鍵值 19 之完整過程,並列出 查找時經過之節點及比較順序。(4 分)
#555987
(一)說明何謂穩定排序(Stable Sort),並解釋若演算法不屬於穩定排序, 在處理相同鍵值時會造成什麼影響。
#555988
(二)使用選擇排序(Selection Sort)對上述數列進行排序,並逐步描述每次 選擇與交換的過程,最後給出排序後的結果。
#555989
(三)使用合併排序(Merge Sort)對上述數列進行排序,並描述拆分與合併 的過程,最後給出排序後的結果。
#555990
(四)使用基數排序(Radix Sort)對上述數列進行排序,並描述逐位(個位 數、十位數)的桶排序(Bucket Sort)過程,最後給出排序後的結果。
#555991
相關試卷
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