106年 - [無官方正解]106 國立臺北大學_學士班曁進修學士班轉學生招生考試試題_資訊工程學系3年級：資料結構#147394

(1)何者為 Linked List 優點 (A)可用 Index 直接查找 Value (B)可動態插入資料 (C)無須使用指標撰寫 (D)資料結構長度不需固定大小

(2)下列何者為系統堆疊的內容 (A) 執行程式碼 (B)回傳地址 (C)函式區域變數 (D)靜態變數

(a). 請利用並顯示各節點 dfn (depth-first number) 及 low (the lowest depth-first number) 值，找出 Figure 1 所有之關節點 (articulation points)。假設利用深度優先搜尋法 (depth first search) 讀取節點之順序為 4-2-1-3-5-6-8-9-7，也就是節點 4 之 dfn 值為 1，節點 2 之 dfn 值為 2，節點 1 之 dfn 值為 3，依此類推。(12%)

(b). 請說明如何判斷一節點為關節點之規則為何？(4%)

(c). low 計算之公式為何？(6%)

2. (16%) 請定義何謂左傾樹(Leftist tree) 並將 Figure 2 之左傾樹加以合併.

3. (12%) 請說明解釋在一非空集合之二元樹，假設 \( n_0 \) 樹葉節點(leaf node)的數目而 \( n_2 \) 為分支度為 2(i.e. degree 2) 節點的數目。請問 \( n_0 \) 和 \( n_2 \) 關係為何？

4. (10%)使用以下 inorder 敘述來呈現 preorder, postorder, and level order:
A*(B+C)/E*F

(a).移動到終點

(b).解決死路

6. (20%)使用 linked list 完成以下 stack 程式