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

(a)找出關節點(articulation points) i.e. 可將圖分解成兩個不連通單元的節點。請利用*dfn* (*depth first number*) 和*low* (*the lowest depth-first number*) 值找出關節點並將*low*值填入下表中。

(b)寫出計算*low*值之公式。

(c)請說明找出關節點的規則。

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 表示法。