阿摩線上測驗
登入
首頁
>
公職◆資料結構
>
113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理：資料結構#124511
> 申論題
題組內容
四、關於紅黑樹（Red Black Tree）與(2,4)-樹((2,4)-Tree)：
(一)請分別說明紅黑樹與(2,4)-樹的定義。（10 分）
相關申論題
(一)列出虛擬碼中 Q(n)的遞迴關係式，並說明此虛擬碼最終計算的是什麼？ （5 分）
#529411
(二)用遞迴函式表示此虛擬碼所使用的乘法運算次數，並用漸進式符號 Big-O 表示此遞迴函式的成長速率。（5 分）
#529412
(三)以遞迴函式表示此虛擬碼的執行時間 T(n)並說明其時間複雜度（以 Big-O 表示） 。（10 分）
#529413
二、請回答下列關於二元樹（Binary Tree）的問題：(一)一個算術運算式（Arithmetic Expression）可以用一個二元樹表示，稱為算術運算樹（Expression Tree），請將下列算術運算式以算術運算樹表示。 ( ( ( 5 + 1 ) ✕ 3 － (7 + 2 ) ) / ( ( ( 2✕8 ) + 5 ) / 7 ) )
#529414
(二)請判斷下列敘述是否正確：“一個算術運算樹是一個滿二元樹（Full Binary Tree, or Proper Binary Tree）”
#529415
(三)子題(一)中的算術運算式是何種順序的運算表示式？請利用其算術運算樹將此運算式表示為一前序表示式（Preorder Expression），並說明其過程。（5 分）
#529416
(四)請敘述如何以子題(一)的算術運算樹計算出算術運算式的值，並逐步表示其過程。 （10 分）
#529417
(一)請說明優先佇列的抽象資料型態（abstract data type, ADT）定義。 （10 分）
#529418
(二)給定一個最小二元堆積（Minimum Heap）H 與一個鍵值 k，在 H 中快速 地找出所有鍵值小於或等於 k 的資料物件。請描述一個有效的方法，此 方法所花的時間（或運算量）與欲找出的資料物件之數量成線性比例。 （5 分）
#529419
(二)考慮下面的紅黑樹（實線節點代表黑色節點，虛線節點代表紅色節 點），代表節點的字元符號可視為鍵值，請說明如何將此紅黑樹轉換為 一個(2,4)-樹，並將其結果畫出。此外，請申論轉換的(2,4)-樹是否唯一。 （10 分）
#529421
相關試卷
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
阿摩線上測驗
登入
阿摩線上測驗
登入