阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
102年 - 關務#18033
> 申論題
二、已知一棵二元樹(binary tree)的前序走訪(preorder traversal)與中序走訪(inorder traversal)之結果分別如下:(每小題10分,共20分) 前序-A B D E G H C F I 中序-D B G E H A C I F (一)請繪出這棵二元樹。 (二)這棵二元樹的後序走訪(postorder traversal)結果為何?
相關申論題
一、關於時間複雜度(time complexity): (一)下列那兩個敘述是錯的?(10分) (A) 0.5n2+100n=O(n2)(B) 1000=O(1)(C) 0.5n+5logn=O(n2) (D) 2n2+5n=O(2n)(E) n7+1.5n=O(n7)(F) 3n2+nlog4n=O(nlog4n) (二)承上,請把上題錯的敘述改正並且寫下。(20分)
#15705
四、考慮排序(sort)的問題:(每小題10分,共30分) (一)如果要排序的資料很少,例如只有十幾筆資料,那麼你將採用快速排序法(quick sort)?合併排序法(merge sort)?還是氣泡排序法(bubble sort)?為什麼? (二)如果要排序的資料很多,例如多到超過主記憶體容量許多,那麼你將採用快速排序法?合併排序法?還是氣泡排序法?為什麼? (三)快速排序法、合併排序法以及氣泡排序法這三個排序法當中,那一(些)排序法是穩定的(stable)?或者都不穩定?
#15708
(三)請分別說明 Binary Search Tree 與 Red Black Tree 在插入、刪除與搜尋數 字等三操作的時間複雜度。(12 分)
#570252
(二)從空集合開始,依下列數字串 1, 2, 3, 4, 5, 6, 7, 8 順序插入節點建立並繪 出 Red Black Tree。(紅色節點請以雙線同心圓表示,例如將紅色節點 5 表示成 ;黑色節點請以單線圓表示,例如將黑色節點 8 表示成 ) 。 (13 分)
#570251
(一)從空集合開始,依下列數字串 1, 2, 3, 4, 5, 6, 7, 8 順序插入節點建立並繪 出 Binary Search Tree。(5 分)
#570250
(三)若 Graph 有 n 個節點與 e 個邊,請分別以 Big O 寫出以 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存 Graph 空間複雜度。比較 且說明兩者在空間複雜度的優劣。(14 分)
#570249
(二)若 Graph 有 n 個節點與 e 個邊,請分別說明並以 Big O 寫出 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存 Graph 時,計算 Graph 中所有節點 Degree 演算法的時間複雜度。(10 分)
#570248
(一)請以下圖的 Graph 為例,分別繪出示意圖,說明程式如何以 adjacency matrix 和 adjacency multilist 二種不同資料結構儲存此 Graph。(6 分)
#570247
二、何謂 Complete Binary Tree?假設單一節點的樹其樹高為 1,證明若 Complete Binary Tree 含 n 個節點且樹高為 h,則 2h-1≤ n ≤2h-1。(20 分)
#570246
(三)若甲、乙二種不同演算法可解決同一問題,甲的時間複雜度為 O(n log n), 乙的時間複雜度為 O(n2)。將此二演算法以程式語言實作,請列舉一類型測試資料,並說明其會使甲演算法程式實際執行時間不一定比乙演算 法程式實際執行時間快。(10 分)
#570245
相關試卷
115年 - 115 關務特種考試_三等_資訊處理(選試英文):資料結構#138980
115年 · #138980
115年 - 115 身心障礙特種考試_三等_資訊處理:資料結構#138979
115年 · #138979
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