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

科目：研究所、轉學考(插大)-資料結構 | 年份：113年 | 選擇題數：0 | 申論題數：12

試卷資訊

所屬科目：研究所、轉學考(插大)-資料結構

選擇題 (0)

申論題 (12)

1. (24分) 請在Figure 1中
假設 Depth First Search 之順序為 4-2-1-3-5-6-8-9-7 也就是節點4之*dfn*值為1，節點2之*dfn*值為2，節點1之*dfn*值為3，依此類推。
(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 表示法。