108年 - 108 公務人員升官等公務薦任_資訊處理：資料結構#80495

科目：公職◆資料結構 | 年份：108年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (14)

⑴考慮中序運算式(6 − 2)×(5+ 9 / 3) + 4×7，請說明其前序與後序運算式分別為何？（8 分）

⑵請說明為何中序運算式需要使用括號來輔助界定運算元的優先順序而前序與後序運算式則無需括號？（7 分）

⑶請說明如何利用一個堆疊（Stack）結構計算出一個後序運算式的值，並以後序運算式 a b × c + d c / −為例，其中 a = 3, b = 5, c = 2, d = 6，請逐步列出運算過程中堆疊的內容。（10 分）

⑴請說明二元搜尋樹的定義？（5 分）

⑵是否可以使用一個二元搜尋樹對鍵值（Key）來進行排序（Sorting）？如果不行，請解釋其原因。若可以，請描述作法及執行時間。（5 分）

⑶ AVL 樹是一個基於二元搜尋樹的資料結構，請敘述 AVL 樹的定義並說明為何一個有 n 個節點（鍵值）的 AVL 樹其高度是 O（log n）。（5 分）

⑷若將鍵值 36、25、14、27、55、30 以依序加入的方式建構一個 AVL 樹，請繪出每次加入後的 AVL 樹。（10 分）

⑴請說明如何利用優先佇列將資料物件以鍵值進行排序。

⑵

⑶

⑷

⑴

⑵

⑶