2. (26分) (a)假設樹有 n 個節點，樹的分支度為 k，共有多少 link 是浪費掉的 (i.e. null links)？(6分)

(b)請說明何謂引線二元樹 (Threaded Binary Trees)？目的為何？(8分)

(c)請針對引線二元樹 (Threaded Binary Trees) 寫出一將 node r 加入到 node S 右邊子節點 (left child) 如 Figure 2所示的演算法。(12分)

3. (16分) (a)請描述 order 為 m 的 B-tree 之特性。

(b)請問 order 為 m 高度為 h 的 B-tree：最少有幾個節點？最少有幾個 Key？

4. (12分) 對於任何非空二元樹 T，如果n₀是葉節點數，n₂是分支度為2之節點數，n₀ 和 n₂ 有什麼關係？請給出你的解釋！

5. (12分) (a)請寫出如何將 Infix 轉成 Postfix 之規則。

(b)請寫出 (A+B)*D+E/(F+A*D)+C 之 postfix 形式。

6. (10分) 請針對 Figure 3 寫出 adjacency multilists 表示法。

Recent demographic data from Taiwan presents a striking sociological phenomenon. The combined population of domestic dogs and cats has officially surpassed the number of children under the age of fourteen. This inversion of traditional household structures is accompanied by a thriving "pet economy," characterised by robust revenue growth in the retailers of pet food and specialised lifestyle services. The latest survey by the Ministry of Agriculture in Taiwan in 2026 also indicates a historic structural shift within this trend, revealing that the domestic cat population (1.74 million) has outnumbered the dog population (1.46 million) for the first time. Please write a well-constructed analytical essay to share your perspective on this trend and discuss the possible factors underpinning this phenomenon. The number of words should be between 500 to 800. (100%)

115年 - 115 國立臺北大學_日間學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147430

115年 - 115 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#143912

114年 - 114 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#144138

113年 - 113 國立臺北大學_日間學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147432

113年 - 113 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#144167

112年 - 112 國立臺北大學_日間學士班轉學生招生考試試題_資訊工程學系日間學士班3年級：資料結構#147429

112年 - 112 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#144165

111年 - 111 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#145441

110年 - 110 國立嘉義大學_碩士班招生考試試題_資訊工程學系：資料結構#145491

110年 - 110 國立臺灣科技大學_碩士班招生試題_電子工程系：資料結構#112844