113年 - 113 地方政府公務、離島地區公務特種考試_三等_資訊處理：資料結構#124511

(一)列出虛擬碼中 Q(n)的遞迴關係式，並說明此虛擬碼最終計算的是什麼？ （5 分）

(二)用遞迴函式表示此虛擬碼所使用的乘法運算次數，並用漸進式符號 Big-O 表示此遞迴函式的成長速率。（5 分）

(三)以遞迴函式表示此虛擬碼的執行時間 T(n)並說明其時間複雜度（以 Big-O 表示） 。（10 分）

二、請回答下列關於二元樹（Binary Tree）的問題：
(一)一個算術運算式（Arithmetic Expression）可以用一個二元樹表示，稱為算術運算樹（Expression Tree），請將下列算術運算式以算術運算樹表示。
 ( ( ( 5 + 1 ) ✕ 3 － (7 + 2 ) ) / ( ( ( 2✕8 ) + 5 ) / 7 ) )

(二)請判斷下列敘述是否正確：
“一個算術運算樹是一個滿二元樹（Full Binary Tree, or Proper Binary Tree）”

(三)子題(一)中的算術運算式是何種順序的運算表示式？請利用其算術運算樹將此運算式表示為一前序表示式（Preorder Expression），並說明其過程。（5 分）

(四)請敘述如何以子題(一)的算術運算樹計算出算術運算式的值，並逐步表示其過程。 （10 分）

(一)請說明優先佇列的抽象資料型態（abstract data type, ADT）定義。 （10 分）

(二)給定一個最小二元堆積（Minimum Heap）H 與一個鍵值 k，在 H 中快速 地找出所有鍵值小於或等於 k 的資料物件。請描述一個有效的方法，此 方法所花的時間（或運算量）與欲找出的資料物件之數量成線性比例。 （5 分）

 (一)請分別說明紅黑樹與(2,4)-樹的定義。（10 分）

(二)考慮下面的紅黑樹（實線節點代表黑色節點，虛線節點代表紅色節 點），代表節點的字元符號可視為鍵值，請說明如何將此紅黑樹轉換為 一個(2,4)-樹，並將其結果畫出。此外，請申論轉換的(2,4)-樹是否唯一。 （10 分）

(三)請說明為何一個有 n 個節點（鍵值）的紅黑樹其高度是 O(log n)。 （5 分）

 (一)請畫出此無向圖 G。（10 分）

(二)若以字母順序為考量對 G 進行廣度優先搜尋（Breadth-First Search, BFS） ，因此將由節點 a 開始，請繪出尋訪完後所產生的 BF 樹 （Breadth- First (BF) Tree）。（5 分）